What is Sorting?
Sorting is the process of arranging the data in a particular order, mostly ascending (low to high) or descending (high to low).
Why do we need data in sorted order?
In programming there is often a need to sort the data for reducing the complexity for further computation for example address book, customer records, contact numbers etc. Data retrieval and search performance can be significantly improved if the data is arranged in the sorted order.
What are the most common sorting algorithms?
There are several sorting algorithms available however below are some of the most commonly used ones –
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
Provide run time complexity comparison for these algo?
| Sorting Algo | Type | Best Case | Avg Case | Worst Case |
| Bubble | Linear | O(n2) | O(n2) | O(n2) |
| Bubble modified | Linear | O(n) | O(n2) | O(n2) |
| Selection | Linear | O(n2) | O(n2) | O(n2) |
| Insertion | Linear | O(n) | O(n2) | O(n2) |
| Merge | Recursive | O(nlogn) | O(nlogn) | O(nlogn) |
| Quick | Recursive | O(nlogn) | O(nlogn) | O(n2) |
| Heap | O(nlogn) | O(nlogn) | O(nlogn) |
Which one is the most efficient sorting algorithm?
Quick sort is considered the most efficient one and implemented as most of the sort functions due to two reasons –
- It is an inplace sorting as compare to merge sort which has the space complexity of O(n).
- The worst case performance O(n2) is mostly avoided and in most of the cases the complexity would be O(nlogn) only, which makes it better choice then merge sort.
Describe bubble sort algorithm?
Compare the elements sequentially until the largest number bubbles up, repeat the process for all the remaining elements, each comparison is known as one pass. No of passes needed is equal to number of elements in the array and number of comparisons is also equal to n, which gives the time complexity of O(n2) in most of the cases.
Algorithm –
Describe selection sort algorithm?
Selection sort works on identify the minimum element in each pass and replacing it with the left element for that pass. The complexity remains O(n2) in most of the cases.
Algorithm –
Describe insertion sort algorithm?
Insertion sorts works by dividing the array into two sub array one is sorted and another one is unsorted, The array is traversed one by one and elements are inserted into the sorted array (left) while it hits the end of array.
This is mostly used for sorting of linked list.
Algorithm –
Describe merge sort algorithm?
Merge sort works by dividing the array into sub arrays until we reach to single element array (Downward) and then merging them (upward), while merging it will make sure that elements are merged into the sorted order.
The algorithm basically contain two functions 1) function is used for dividing the array into sub array 2) function is used for merging the two sub arrays.
Thought the run time complexity is of O(nlogn) it also has the space complexity of additional storage needed to create the sub arrays.
Algorithm –
Describe quick sort algorithm?
Quick sort is an in place divide and conquer algorithm, it does not use an additional space while performing the sort operation. The general logic works upon identifying the pivot element (can be left most of right most element) and then partitioning the elements in the such a way that smaller elements are on the left side and higher elements are on the right side, the position of the pivot once the array is partitioned is returned as partition index for subsequent sorting of left and right partitions using the recursive call.
It usually consists of two functions 1) quicksort 2)partition, run time complexity is mostly O(nlogn) where worst case is O(n2) which can be avoided by randomizing the pivot selection.
Algorithm –
techprepblog 