Why do we study the design, analysis, and comparison of sorting algorithms in data structures? Here are some critical reasons:
Based on their importance, we need to understand the critical comparisons between various sorting algorithms based on different parameters such as time complexity, space complexity, in-place sorting, stability, online vs. offline sorting, etc.
In comparison-based sorting algorithms, we get the sorted order output by comparing elements in the input. It's important to note that all comparison-based sorting algorithms have a lower bound of O(nlogn). In other words, any comparison-based sorting algorithm will take at least O(nlogn) time to sort an array of n elements.
Here are some examples of sorting algorithms which use comparison as a critical operation to complete the sorting process:
The worst-case time complexities of the above sorting algorithms will be categorized into two parts: O(n^2) sorting and O(nlogn) sorting.
In addition to the comparison operations, these sorting algorithms also use other types of operations.
However, the count of these operations will always be less than or equal to the count of comparison operations. That's why the comparison operation is the deciding factor for the time complexity in the above sorting algorithms.
There are sorting algorithms that have a faster time complexity than O(nlogn), but they require special assumptions about the input sequence to determine the sorted order. These sorting algorithms use operations other than comparisons to determine the sorted order, and they work in O(n) time complexity. So, the lower bound of O(nlogn) does not apply to these sorting algorithms.
Examples of sorting algorithms that run in linear time are counting sort, radix sort, and bucket sort. Counting sort and radix sort assume that the input consists of integers in a small range. Meanwhile, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval [0, 1).
Here is a comparison of the time and space complexities of some popular sorting algorithms:
An "in-place" sorting algorithm sorts the elements without using extra memory. Here we store a constant number of elements temporarily outside the array while sorting.
Examples of in-place sorting algorithms are bubble sort, selection sort, insertion sort, quicksort, and heapsort. In contrast, merge sort and counting sort are not in-place algorithms as they require additional memory.
A sorting algorithm is "stable" if it preserves the relative order of elements with the same value. For example, if A[i] is equal to A[j] and i < j, then A[i] must appear before A[j] in the sorted output.
We can make non-stable sorting algorithms stable by extending the comparison operation to include tie-breaking rules based on the order of the original input. But this process may require additional time and space to remember the original order.
An algorithm that sorts data as it becomes available is called an "online" sorting algorithm. Such algorithms sequentially process input data and allow sorting to occur before the entire input set is available.
For example, insertion sort considers one input element at a time and places that element in a partially sorted array. This will maintain a sorted output by inserting each new input element in its proper place as it becomes available. So, insertion sort is an online sorting algorithm.
In contrast, an "offline" algorithm requires all input data to be present in memory before sorting can start. For example, the selection sort algorithm sorts an array by finding the minimum element in the unsorted part and placing it in the partially sorted array. This process requires access to the entire input. So, selection sort is an offline sorting algorithm.
Learning sorting algorithms is an effective idea for mastering problem-solving and time complexity analysis of algorithms. Sorting is also frequently used as a key technique to solve various coding problems.
The choice of the best sorting algorithm depends on several factors, including the size of the input data, the order of the data, memory usage, stability, performance, etc.
Enjoy learning, Enjoy sorting!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.