Lecture 7: Linear-Time Sorting Lecture Overview • Comparison model • Lower bounds – searching: Ω(lg n) – sorting: Ω(n lg n) • O(n) sorting algorithms for small integers – counting sort – radix sort Lower Bounds Claim • searching among n preprocessed items requires Ω(lg n) time =⇒ binary search, AVL tree search optimal theorem proof counterexample • sorting n items requires Ω(n lg n) =⇒ mergesort, heap sort, AVL sort optimal . . . in the comparison model Comparison Model of Computation • input items are black boxes (ADTs) • only support comparisons (<, >, ≤, etc.) • time cost = # comparisons Decision Tree Any comparison algorithm can be viewed/specified as a tree of all possible comparison outcomes & resulting output, for a particular n: • example, binary search for n = 3: 1 A[1] < x? NO NO x ≤A[0] YES A[2] < x? A[0] < x? YES NO A[0] < x ≤ A[1] A[1] < x ≤ A[2] YES A[2] < x • internal node = binary decision • leaf = output (algorithm is done) • root-to-leaf path = algorithm execution • path length (depth) = running time • height of tree = worst-case running time In fact, binary decision tree model is more powerful than comparison model, and lower bounds extend to it Search Lower Bound • # leaves ≥ # possible answers ≥ n (at least 1 per A[i]) • decision tree is binary • =⇒ height ≥ lg Θ(n) = lg n ±Θ(1) | {z } lg Θ(1) Sorting Lower Bound • leaf specifies answer as permutation: A[3] ≤ A[1] ≤ A[9] ≤ . . . • all n! are possible answers 2 • # leaves ≥ n! =⇒ height ≥ lg n! = lg(1 · 2 · · · (n − 1) · n) = lg 1 + lg 2 + · · · + lg(n − 1) + lg n n X = lg i ≥ ≥ i=1 n X i=n/2 n X i=n/2 lg i n lg 2 |{z} =lg n−1 = n n lg n − = Ω(n lg n) 2 2 • in fact lg n! = n lg n − O(n) via Sterling’s Formula: n! ∼ √ 2πn n n e =⇒ lg n! ∼ n lg n − (lg e)n + 21 lg n + 21 lg(2π) | {z } O(n) Linear-time Sorting If n keys are integers (fitting in a word) ∈ 0, 1, . . . , k − 1, can do more than compare them • =⇒ lower bounds don’t apply • if k = nO(1) , can sort in O(n) time OPEN: O(n) time possible for all k? Counting Sort L = array of k empty lists — linked or Python lists ) for j in range n: L[key(A[j])].append(A[j]) → O(1) | {z } random access using integer key    O(n) output = [ ] for i in range k: output.extend(L[i])  P   O( i (1 + |L[i]|)) = O(k + n)     3 O(k) Time: Θ(n + k) — also Θ(n + k) space Intuition: Count key occurrences using RAM output copies of each key in order . . . but item is more than just a key CLRS has cooler implementation of counting sort with counters, no lists — but time bound is the same Radix Sort • imagine each integer in base b =⇒ d = logb k digits ∈ {0, 1, . . . , b − 1} • sort (all n items) by least significant digit → can extract in O(1) time • ··· • sort by most significant digit → can extract in O(1) time sort must be stable: preserve relative order of items with the same key =⇒ don’t mess up previous sorting For example: 3 4 6 8 4 7 3 2 5 5 3 3 2 5 9 7 7 9 6 0 5 7 3 4 4 6 3 8 sort 2 5 3 5 5 2 3 0 5 6 7 7 9 9 7 3 4 8 3 4 6 sorted 2 2 3 3 5 5 5 0 9 6 9 5 7 7 sorted • use counting sort for digit sort – =⇒ Θ(n + b) per digit – =⇒ Θ((n + b)d) = Θ((n + b) logb k) total time – minimized when b = n – =⇒ Θ(n logn k) – = O(nc) if k ≤ nc 4 3 3 4 4 6 7 8 2 5 3 5 5 2 3 9 5 6 7 7 0 9 sorted

6.006 Lecture 7: Counting Sort, Radix Sort, Lower Bounds for Sorting

Related Documents

Recommended Documents

Description

Related Documents

Want to Download This Document?

Free up your schedule!

Take 5 seconds to unlock