Sorting is one of the fundamental coding problems in data structure and algorithms. The critical question is: why do we study the design and analysis of the sorting algorithms? Here are some critical reasons:
The sorting problem can be solved using various ideas. So sorting algorithm is one of the best ideas to learn different problem-solving approaches. For example:
Incremental approach: Bubble sort, Selection, and Insertion sort are based on this idea where we incrementally build a partial solution. At each outer loop iteration, we place one value to the correct position on the sorted output. In other words, at each iteration of the outer loop, the unsorted sort will decrease by 1, and the partially sorted array size will increase by 1.
Two pointers approach: The merging process in the merge sort and the partition process in quicksort are good examples of the two pointers approach. We move both pointers forward and build the partial solution based on the condition.
Problem-solving using a data structure: Heap sort and BST sort are good examples. In the heap sort, we first build the max-heap structure of the input and continuously perform the deletion of the max element with the heapify operation. Similarly, in the BST sort, we first create a BST of the given input and traverse the tree using in-order traversal to generate the sorted output. The good thing is that both sorting algorithms work in O(nlogn) time complexity. On the other side, linear time sorting algorithms like counting sort and bucket sort use the direct addressing idea of hashing to sort the input given in a particular range.
Sometimes, organizing the data into sorted order can help us solve coding problems efficiently. In other words, sorting is also a problem-solving approach in DSA. For example, after organizing the data in sorted order, we can perform a single scan, apply a binary search, or use a two-pointers approach to get the desired output.
Sometimes, we inherently need sorting algorithms in our applications. For example, contact numbers are organized in sorted order of name on mobile phones. Similarly, several algorithms use sorting as a subroutine for their solution. For example, advanced algorithms like "finding the closest pair of points" and "finding convex hull" use sorting to pre-process input.
Here is some problem that uses sorting:
Sorting is one of the best algorithms to learn recursion and iteration's time and space complexity analysis. For example, analysis of Bucket sort, Insertion sort, Selection sort, Heap sort, and Counting sort are good ideas to learn the best, worst and average case analysis of various types of loops. Similarly, analysis of merge sort and quick sorts are good ideas for learning recursion analysis.
Other than organizing data in increasing or decreasing order, there are a lot of variations available to the sorting problems. On the other hand, sorting algorithms are good to learn: how to handle several boundary conditions (base case, initialization, termination, post-termination situation, a scenario of repeated elements, etc.) in iterative and recursive code.
Here are some popular variations of sorting problems:
Sorting algorithms are good ideas to learn code optimization approaches. For example, we can optimize bubble sort code using a flag variable, insertion sort code using binary search, quick-sort code using the idea of insertion sort, etc.
Enjoy learning, Enjoy sorting!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.