L9 - Sorting in Linear Time.pdf

CP312 Algorithm Design and Analysis I LECTURE 9: SORTING IN LINEAR TIME 1 Comparison-based Sorting All the sorting algorithms we have seen so far are comparison sorts. That is, they only use comparisons to determine relative order of elements. Is there a comparison sort that can do better than 𝑂(𝑛 l...

CP312 Algorithm Design and Analysis I LECTURE 9: SORTING IN LINEAR TIME 1 Comparison-based Sorting All the sorting algorithms we have seen so far are comparison sorts. That is, they only use comparisons to determine relative order of elements. Is there a comparison sort that can do better than 𝑂(𝑛 lg 𝑛)? ◦ Answer: NO! ◦ Any comparison-based sorting algorithm must do at least 𝑛 lg 𝑛 amount of work in the worst-case 2 Sorting in Linear Time Is there any way to sort without doing comparisons? And if there is, how fast can they get? 3 Counting Sort Input: 𝐴[1, … , 𝑛] where 𝐴 𝑗 ∈ {1, … , 𝑘} Output: 𝐴′ [1, … , 𝑛] which is 𝐴 sorted Takes time Θ(𝑛 + 𝑘) So if 𝑘 = 𝑂(𝑛) then it would take time Θ(𝑛) 4 Counting Sort Initialize 𝐶 1, … , 𝑘 ← [0, … , 0] for 𝑖 = 1 to 𝑛 𝐶 𝐴 𝑖 ←𝐶 𝐴 𝑖 +1 for 𝑖 = 2 to 𝑘 𝐶 𝑖 ← 𝐶 𝑖 + 𝐶[𝑖 − 1] for 𝑖 = 𝑛 to 1 𝐴′ 𝐶 𝐴 𝑖 𝐶𝐴𝑖 ←𝐴𝑖 ←𝐶 𝐴 𝑖 −1 5 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 Initialize 𝐶 1, … , 𝑘 ← [0, … , 0] 𝐶 1 2 3 4 0 0 0 0 𝑘=4 6 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 0 0 0 0 for 𝑖 = 1 to 𝑛 𝐶 𝐴𝑖 ←𝐶 𝐴 𝑖 +1 7 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 0 0 0 1 for 𝑖 = 1 to 𝑛 𝐶 𝐴𝑖 ←𝐶 𝐴 𝑖 +1 8 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 0 0 1 for 𝑖 = 1 to 𝑛 𝐶 𝐴𝑖 ←𝐶 𝐴 𝑖 +1 9 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 0 1 1 for 𝑖 = 1 to 𝑛 𝐶 𝐴𝑖 ←𝐶 𝐴 𝑖 +1 10 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 0 1 2 for 𝑖 = 1 to 𝑛 𝐶 𝐴𝑖 ←𝐶 𝐴 𝑖 +1 11 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 0 2 2 for 𝑖 = 1 to 𝑛 𝐶 𝐴𝑖 ←𝐶 𝐴 𝑖 +1 12 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 0 2 2 for 𝑖 = 2 to 𝑘 𝐶 𝑖 ← 𝐶 𝑖 + 𝐶[𝑖 − 1] 13 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 2 2 for 𝑖 = 2 to 𝑘 𝐶 𝑖 ← 𝐶 𝑖 + 𝐶[𝑖 − 1] 14 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 3 2 for 𝑖 = 2 to 𝑘 𝐶 𝑖 ← 𝐶 𝑖 + 𝐶[𝑖 − 1] 15 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 3 5 for 𝑖 = 2 to 𝑘 𝐶 𝑖 ← 𝐶 𝑖 + 𝐶[𝑖 − 1] 16 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 3 5 for 𝑖 = 𝑛 to 1 𝐴′ 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 17 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 3 5 for 𝑖 = 𝑛 to 1 𝐴′ 3 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 18 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 2 5 for 𝑖 = 𝑛 to 1 𝐴′ 3 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 19 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 2 5 for 𝑖 = 𝑛 to 1 𝐴′ 3 4 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 20 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 2 4 for 𝑖 = 𝑛 to 1 𝐴′ 3 4 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 21 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 2 4 for 𝑖 = 𝑛 to 1 𝐴′ 3 3 4 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 22 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 1 4 for 𝑖 = 𝑛 to 1 𝐴′ 3 3 4 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 23 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 1 1 1 4 for 𝑖 = 𝑛 to 1 𝐴′ 1 3 3 4 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 24 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 0 1 1 4 for 𝑖 = 𝑛 to 1 𝐴′ 1 3 3 4 4 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 25 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 0 1 1 3 for 𝑖 = 𝑛 to 1 𝐴′ 1 3 3 4 4 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 26 Counting Sort: Example 𝐴 1 2 3 4 5 4 1 3 4 3 𝐶 1 2 3 4 0 1 1 3 for 𝑖 = 𝑛 to 1 𝐴′ 1 3 3 4 4 𝐴′ 𝐶 𝐴 𝑖 𝐶 𝐴𝑖 ←𝐴 𝑖 ←𝐶 𝐴 𝑖 −1 27 Counting Sort: Running-Time Analysis Initialize 𝐶 1, … , 𝑘 ← [0, … , 0] for 𝑖 = 1 to 𝑛 𝐶 𝐴 𝑖 ←𝐶 𝐴 𝑖 +1 for 𝑖 = 2 to 𝑘 𝐶 𝑖 ← 𝐶 𝑖 + 𝐶[𝑖 − 1] for 𝑖 = 𝑛 to 1 𝐴′ 𝐶 𝐴 𝑖 𝐶𝐴𝑖 ←𝐴𝑖 Θ(𝑘) Θ(𝑛) Θ(𝑘) 𝑇 𝑛 = Θ(𝑛 + 𝑘) Θ(𝑛) ←𝐶 𝐴 𝑖 −1 28 Stability in Sorting Counting sort is a stable sort: it preserves the input order among equal elements. 𝐴 4 1 3 4 3 𝐴 4 1 3 4 3 𝐴′ 1 3 3 4 4 𝐴′ 1 3 3 4 4 Stable Not Stable 29 An Issue with Counting Sort Suppose we want to sort the following array using counting sort. 329 457 657 839 436 720 355 We need to create a HUGE auxiliary storage array to count them since the range 𝑘 is large. 329 330 331 332 1 0 0 0 838 839 …….. 0 1 30 Radix Sort Digit-by-digit sorting on least significant digit first. Requires an auxiliary stable sort 329 457 657 839 436 720 355 31 Radix Sort 3 2 9 7 2 0 7 2 0 3 2 9 4 5 7 3 5 5 3 2 9 3 5 5 6 5 7 Counting Sort 4 3 6 Counting Sort 4 3 6 Counting Sort 4 3 6 8 3 9 4 5 7 8 3 9 4 5 7 4 3 6 6 5 7 3 5 5 6 5 7 7 2 0 3 2 9 4 5 7 7 2 0 3 5 5 8 3 9 6 5 7 8 3 9 32 Analysis of Radix Sort Each pass in the for loop takes O(n+k). We have d passes => O(dn+dk). When k = O(n) => O(dn+dn) = O(2dn) = O(n) (Assuming that d is a constant). 33 Summary of Sorting Algorithms Algorithm In-Place Θ 𝑛2 Y Merge sort Θ 𝑛 lg 𝑛 Θ 𝑛 lg 𝑛 N Quicksort Θ(𝑛2 ) Θ(𝑛 lg 𝑛) Y Expected: Θ 𝑛 lg 𝑛 - Y BST-Sort Θ(𝑛2 ) Θ(𝑛 lg 𝑛) Y Heapsort 𝑂(𝑛 lg 𝑛) 𝑂(𝑛 lg 𝑛) Y Counting Sort Θ(𝑘 + 𝑛) Θ(𝑘 + 𝑛) N Θ 𝑑 𝑘+𝑛 Θ 𝑑 𝑘+𝑛 N Randomized Quicksort Distributionbased Sorts Average-Case Running Time Θ 𝑛2 Insertion Sort Comparisonbased Sorts Worst-Case Running Time Radix Sort 34