Introduction to Algorithms 6.046J/18.401JHow fast can we sort?Decision-tree exampleDecision-tree exampleDecision-tree exampleDecision-tree exampleDecision-tree exampleDecision-tree modelLower bound for decision-tree sortingLower bound for comparison sortingSorting in linear timeCounting sortCounting-sort exampleLoop 1Loop 2Loop 2Loop 2Loop 2Loop 2Loop 3Loop 3Loop 3Loop 4Loop 4Loop 4Loop 4Loop 4AnalysisRunning timeStable sortingRadix sortOperation of radix sortCorrectness of radix sortCorrectness of radix sortCorrectness of radix sortAnalysis of radix sortAnalysis (continued)Choosing rConclusionsAppendix: Punched-card technologyHerman Hollerith (1860-1929)Punched cardsHollerith’s tabulating systemOperation of the sorterOrigin of radix sort“Modern” IBM cardWeb resources on punched-card technologySeptember 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.1Prof. Erik DemaineLECTURE 5Sorting Lower Bounds• Decision treesLinear-Time Sorting• Counting sort• Radix sortAppendix: Punched cardsIntroduction to Algorithms6.046J/18.401JSeptember 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.2How fast can we sort?All the sorting algorithms we have seen so far are comparison sorts: only use comparisons to determine the relative order of elements.• E.g., insertion sort, merge sort, quicksort, heapsort.The best worst-case running time that we’ve seen for comparison sorting is O(nlgn).Is O(nlgn) the best we can do?Decision trees can help us answer this question.September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.3Decision-tree example1:21:22:32:31231231:31:31321323123121:31:32132132:32:3231231321321Each internal node is labeled i:j for i, j ∈ {1, 2,…, n}.•The left subtree shows subsequent comparisons if ai≤ aj.•The right subtree shows subsequent comparisons if ai≥ aj.Sort 〈a1, a2, …, an〉September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.4Decision-tree example1:21:22:32:31231231:31:31321323123121:31:32132132:32:3231231321321Each internal node is labeled i:j for i, j ∈ {1, 2,…, n}.•The left subtree shows subsequent comparisons if ai≤ aj.•The right subtree shows subsequent comparisons if ai≥ aj.9 ≥ 4Sort 〈a1, a2, a3〉= 〈 9, 4, 6 〉:September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.5Decision-tree example1:21:22:32:31231231:31:31321323123121:31:32132132:32:3231231321321Each internal node is labeled i:j for i, j ∈ {1, 2,…, n}.•The left subtree shows subsequent comparisons if ai≤ aj.•The right subtree shows subsequent comparisons if ai≥ aj.9 ≥ 6Sort 〈a1, a2, a3〉= 〈 9, 4, 6 〉:September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.6Decision-tree example1:21:22:32:31231231:31:31321323123121:31:32132132:32:3231231321321Each internal node is labeled i:j for i, j ∈ {1, 2,…, n}.•The left subtree shows subsequent comparisons if ai≤ aj.•The right subtree shows subsequent comparisons if ai≥ aj.4 ≤ 6Sort 〈a1, a2, a3〉= 〈 9, 4, 6 〉:September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.7Decision-tree example1:21:22:32:31231231:31:31321323123121:31:32132132:32:3231231321321Each leaf contains a permutation 〈π(1), π(2),…, π(n)〉 to indicate that the ordering aπ(1)≤ aπ(2)≤ L ≤ aπ(n)has been established.4 ≤ 6 ≤ 9Sort 〈a1, a2, a3〉= 〈 9, 4, 6 〉:September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.8Decision-tree modelA decision tree can model the execution of any comparison sort:• One tree for each input size n. • View the algorithm as splitting whenever it compares two elements.• The tree contains the comparisons along all possible instruction traces.• The running time of the algorithm = the length of the path taken.• Worst-case running time = height of tree.September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.9Lower bound for decision-tree sortingTheorem. Any decision tree that can sort n elements must have height Ω(nlgn).Proof. The tree must contain ≥ n! leaves, since there are n! possible permutations. A height-hbinary tree has ≤ 2hleaves. Thus, n! ≤ 2h.∴ h ≥ lg(n!) (lg is mono. increasing)≥ lg ((n/e)n) (Stirling’s formula)= n lg n – n lg e= Ω(n lg n).September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.10Lower bound for comparison sortingCorollary. Heapsort and merge sort are asymptotically optimal comparison sorting algorithms.September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.11Sorting in linear timeCounting sort: No comparisons between elements.• Input: A[1 . . n], where A[j]∈{1, 2, …, k}.• Output: B[1 . . n], sorted.• Auxiliary storage: C[1 . . k].September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.12Counting sortfor i ← 1 to kdo C[i] ← 0for j ← 1 to ndo C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}|for i ← 2 to kdo C[i] ← C[i] + C[i–1] ⊳ C[i] = |{key ≤ i}|for j ← n downto 1do B[C[A[ j]]] ← A[ j]C[A[ j]] ← C[A[ j]] – 1September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.13Counting-sort exampleA:4411334433B:12345C:1234September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.14Loop 1A:4411334433B:12345C:000000001234for i ← 1 to kdo C[i] ← 0September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.15Loop 2A:4411334433B:12345C:000000111234for j ← 1 to ndo C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}|September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.16Loop 2A:4411334433B:12345C:110000111234for j ← 1 to ndo C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}|September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.17Loop 2A:4411334433B:12345C:110011111234for j ← 1 to ndo C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}|September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.18Loop 2A:4411334433B:12345C:110011221234for j ← 1 to ndo C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}|September 26, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L5.19Loop 2A:4411334433B:12345C:110022221234for j ← 1 to ndo C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}|September 26, 2005 Copyright © 2001-5 Erik