Question

For your initial post, utilizing credible sources, describe the various types of sorting and searching algorithms and give an example of each other than the examples provided in the assigned readings. Apply algorithmic design and data structure techniques in developing structured programs by discussing time and space complexity in relation to whether using a sort algorithm is better than using a search algorithm. Does it really matter with the capabilities of computers today? Provide justification to support your answers.

Answer 1

The time complexity and space complexity are the two factors used to measure the efficiency of algorithms. But there is always a trade-off between these two. Means to gain time complexity, one should compromise with space and similarly on has to compromise with time to gain space efficiency. But, compromising with the space for time is more prevalent than compromising with the time for space. Nowadays both factors are outdated as we have such a high-speed processor and technologies to upgrade the memory.

Every sorting algorithm has two impotant properties: * Stable * In-place

A sorting algorithm is said to be stable if two equal elements preserve their relative order before and after sorting.

A soring algorithm said to be in-place if it does not require extra memory to sort except few bytes. Not every algorithm is stable and inplace. For example Merge sort is stable and is not in-lace because it requires an extra array to perform sorting.

There are ample of applications of sorting:

* Our contacts in the phone are in sorted order *

  * All the online stores like Amazon, Flipkart places the items based on price and ratings in an sorted order.

* I would like to search a book in the library very fast. Books are placed in an alphabetical order.

There are numerous types of sorting algorithms, in order to keep the elements in sorted order. Few algorithm's performance is good for a small set of input whereas other algorithm's performance is excellent for large input size. Depending on the size and nature of the input , we have to select the sorting algorithm. Let us discuss the various algorithms with the few important parameters.

i) Selection Sort : This algorithm works better if the element list is partially sorted. It is best algorithm when memory space is limited. Time complexity is always quadratic, ie O(n²). Working of this algorithm is based on Brute Force approach.

ii) Insertion sort: It performs the soring in linear time, if the list is almost sorted. Worst case efficiency is same as selection sort, ie O(n²). Best example is: when you try to sort a playing cards in your  hand. It works based on the Decrease and Conquer design strategy algorithm.

iii) Bubble Sort: It requires (n-1) number of passes to sort the elements. After every pass, it slowly bubbles up a smallest element on the top, and biggest element settles in the bottom.  It is more suitable for small size input and time complexity is O(n²). It is easy to understand and implement. Working of this algorithm is based on Brute force approach. Best example is : When a sports teacher asked you to line up in an ascending order of height during school days. The person with a higher height slowly moves backwards and the one with a smaller come in the front. This is how this technique comes in handy

iv) Merge sort : Most efficient algorithm whose time efficiency is : O(n log n). It works based on Divide and Conquer design strategy of algorithms. Best example is : When you want to cut a water melon fruit into 8 or 16 pieces, you do it gradually. You first cut into two halves and then you perform the same steps until you get as many small pieces as you want. Nobody cuts directly the fruit into required number of pieces like 16 or 32. This is about Dividing Phase. In conquer Phase these small pieces are sorted and merged. Which is not directly applicable to this example.

v) Quick Sort: It is also based on DIvide and Conquer design strategy of algorithms. Its performnace depends on the number and position of partitions. If the input list is already in a partially sorted ( either ascending or descending) order, results in more number of partitions on the extreme side of the list. Hence in this situation its performance is O(n²). But if the nature of the input is random, and partitions happens to be in the mid of the list, its performance is same as merge sort algorithm which is O( n log n).

vi) Heap Sort : It is a tree based sorting technique and works based on Transform and Conquer technique. Its efficiency is same as merge sort algorithm efficiency. O(n log n). This algorithm is used very rarely.

Apart from these there are many more types of sorting like Radix sort , Shell sort , Binary sort, Count sort, Bucket sort, etc. But election of these algorithms depends on the data size and their efficiency.

Now, Searching algorithms can not be compared with the sorting, but there is an association between searching and sorting. Searching is impractical and impossible without sorting. In fact sorting is one of the prereqisite for binary search.For example searching a word in a language dictionary is impractical if words in the dictionary is not in an sorted order.

There are two types of searhing algorithms: Linear Search and Binary Search

Linear search: Here, the key element is compared with every element. Worst case efficiency is : O(n), Best case efficiency is : O(1), assuming that element is present at the first position. Average case efficiency is :O(n/2).

Binary Search: Here the pre-requisite is to keep the elements in sorted order. In binary Search, the list is divided into two halves and Key element is compared with mid and if key element falls in the first half, then element is serached only in the first half. As a result half the number of comparisions are reduced in every iteration as compared with linear search. Its best case is O(1) where mid element is the key element and Wors case is O(log n).