Time Complexity Of The Most Popular Sorting Algorithms

In this article, we will discuss the time complexity of some of the most popular sorting algorithms.

The Most Popular Sorting Algorithms

The algorithms that we will be discussing today are listed below

1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Heap Sort

Please note that N denotes the total number of elements present in the vector.

Time Complexity Of Popular Sorting Algorithms

Sorting AlgorithmBest CaseAverage CaseWorst CaseBubble SortO(N)O(N2)O(N2)Selection SortO(N2)O(N2)O(N2)Insertion SortO(N)O(N2)O(N2)Merge SortO(Nlog2N)O(Nlog2N)O(Nlog2N)Quick SortO(Nlog2N)O(Nlog2N)O(N2)Heap SortO(Nlog2N)O(Nlog2N)O(Nlog2N)Combined Complexity Table for Popular Sorting Algorithms

Let’s expand on the time complexity of the most popular sorting algorithms in this list one, by one.

Naive Sorting Algorithms

1. Bubble Sort: This sorting technique involves the comparison of two adjacent elements of the vector. If we are sorting in ascending order then the one which turns out to be greater among the two is pushed towards the right and the smaller element is pushed towards the left.

Bubble sorting involves the usage of two nested for loops, each making nearly N iterations. Hence the overall time complexity of bubble sort is quadratic with N

2. Selection Sort: In this method of sorting we select one element from the vector at a time, compare it with all the other elements, and decide the correct position of this particular element in the vector.

It takes N iterations for finding the correct position for one element, and for the total N elements. Effectively it requires O(NxN) iterations. Hence this sorting technique is also quadratic in nature

3. Insertion Sort: It is very similar to sorting cards. Divide the vector into two parts, one sorted and the other one unsorted. Now, we insert cards(elements) from the unsorted part into the sorted part at their correct position. This method is also quadratic with N.

More Efficient Sorting Algorithms

4. Merge Sort: Alright, so this is also a very popular Divide and Conquer algorithm. In this method, the vector is divided into two smaller sub vectors and these vectors are further divided into smaller subparts until the subparts contain less than or equal to two elements. This is the base case, and we sort these smallest instances of the vectors. The last part involves merging these smaller sorted subarrays.

Merge sort is linear in nature for each subarray and in total we have log2N smaller instances.

5. Quick Sort: In the quick sort method, an element from the vector is selected. We call this selected element Pivot. We shift all the remaining elements smaller than pivot to its left. Shift all the elements greater than the pivot to its right. Repeating this procedure sorts the vector very efficiently.

6. Heap Sort: We generate a heap using the elements of the vector. This heap can either be a max or a min-heap. The generation of heap takes log2N time. We then extract the topmost element from the heap and this also takes log2N iterations. Effectively, extracting N elements would take Nlog2N iterations.

Conclusion

In this article, we discussed the time complexities of the most popular sorting algorithms used to sort data structures. Initially, we considered some naive sorting algorithms. But, later we also discussed the time complexity of some of the most efficient sorting algorithms. Please note that, among all the sorting algorithms that we discussed, quicksort is the fastest(Most Efficient). And, Hoarse-Quicksort is the fastest among all the sorting algorithms, it is the algorithm used by the sort function provided by STL(Standard Template Library).

References

To learn more about sorting algorithms and their time complexity, you can refer to the following sites:

Wikipedia