Linear Sorting
Comparison Sort
- All the sorting algorithms we have seen so far are comparison sorts, which only use comparisons to determine the relative order of elements.
- Such examples are Insertion Sort, Merge Sort, Quick Sort, and Heap Sort.
- The best worst-case running time that we've seen for comparison sorting is O(NlogN).
- A decision tree can model the execution of any comparison sort.
- The tree contains the comparisons along all possible instruction traces.
- The running time of the algorithm is equivalent to the length of the path take, and the worst-time running time is equivalent to the height of the tree.
- Using Stirling's formula, we can prove this theorem.
Counting Sort
- In Counting Sort there is no comparisons between elements.
- The biggest value k within the Input array is an important factor in Counting Sort.
- To analyze the running time of Counting Sort, k term comes into account.
- If k=O(N), then counting sort takes O(N) time.
- However, since k affects the running time, Counting Sort is faster than other comparison sorts in restricted conditions.
Radix Sort
- The key idea of Radix Sort is to sort on least-significant digit first with auxiliary stable sort.
- Assuming that the numbers are sorted by their low-order t-1 digits, sort on digit t.
- Before running Radix Sort, we should first determine the size of digit, r.
- r determines the scale of digits.
- For example, if we choose r=4, there would be 4 passes with each range [0,255].
- If we choose r=16, there would be 2 passes with each range [0, 2^16].
- It is important to choose the optimal r value.
- If each b-bit element is broken into r-bit pieces, each pass of counting sort takes O(n+ 2^r) time.
- We should choose r to minimize T(n,b).
- Increasing r means fewer passes, but as r>>lgN, the time grows exponentially.
- Choosing r=lgn implies T(n,b) = O(bn/lgN).
- In practice, radix sort is fast for large inputs, as well as simple to code and maintain.