6.006- Introduction to Algorithms Lecture 10 Prof. Constantinos Daskalakis CLRS 8.1-8.4Menu • Show that Θ(n lg n) is the best possible running time for a sorting algorithm. • Design an algorithm that sorts in Θ(n) time. • Hint: maybe the models are different ?Comparison 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., merge sort, heapsort. The best running time that we’ve seen for comparison sorting is O(n lg n) . Is O(n lg n) the best we can do? Decision trees can help us answer this question.Decision-tree 1:2 2:3 123 1:3 132 312 1:3 213 2:3 231 321 A recipe for sorting n numbers 〈a1, a2, …, an〉$≥ ≤ - Branching direction depends on outcome of comparisons. - Nodes are suggested comparisons: i:j means compare ai to aj, for i, j ∈ {1, 2,…, n}. ≥ ≤ ≥ ≤ ≥ ≤ ≥ ≤ - Leaves are labeled with permutations corresponding to the outcome of the sorting.Decision-tree example 1:2 2:3 123 1:3 132 312 1:3 213 2:3 231 321 Each 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 ≥ 4 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉:$1:2Decision-tree example 1:2 2:3 123 1:3 132 312 1:3 213 2:3 231 321 Each 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 ≥ 6 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉:$Decision-tree example 1:2 2:3 123 1:3 132 312 1:3 213 2:3 231 321 Each 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 ≤ 6 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉:$Decision-tree example 1:2 2:3 123 1:3 132 312 1:3 213 2:3 231 321 Each leaf contains a permutation 〈π(1), π(2),…, π(n)〉 to indicate that the ordering aπ(1) ≤ aπ(2) ≤ ≤ aπ(n) has been established. 4 ≤ 6 ≤ 9 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉:$Decision-tree model A decision tree can model the execution of any comparison sort: • One tree for each input size n. • A path from the root to the leaves of the tree represents a trace of comparisons that the algorithm may perform. • The running time of the algorithm = the length of the path taken. • Worst-case running time = height of tree.Lower bound for decision-tree sorting Theorem. Any decision tree that can sort n elements must have height Ω(n lg n) . Proof. (Hint: how many leaves are there?) • The tree must contain ≥ n! leaves, since there are n! possible permutations • A height-h binary tree has ≤ 2h leaves • Thus $2h ≥ n! h ≥ lg(n!) (lg is mono. increasing) ≥ lg ((n/e)n) (Stirling’s formula) = n lg n – n lg e = Ω(n lg n) .Sorting in linear time Counting sort: No comparisons between elements. • Input: A[1 . . n], where A[ j]∈{1, 2, …, k} . • Output: B[1 . . n], a sorted permutation of A • Auxiliary storage: C[1 . . k] .Counting sort for i ← 1 to k do C[i] ← 0 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 for i ← 2 to k do C[i] ← C[i] + C[i–1] for j ← n downto 1 do B[C[A[ j]]] ← A[ j] C[A[ j]] ← C[A[ j]] – 1 using cumulative frequencies build sorted permutation store in C the frequencies of the different keys in A i.e. C[i] = |{key = i}| now C contains the cumulative frequencies of different keys in A, i.e. C[i] = |{key ≤ i}|Counting-sort example A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 2 3 4 one index for each possible key stored in ALoop 1: initialization A: 4 1 3 4 3 B: 1 2 3 4 5 C: 0 0 0 0 for i ← 1 to k do C[i] ← 0 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 0 0 0 1 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 0 0 1 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 0 1 1 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 0 1 2 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 0 2 2 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 B: 1 2 3 4 5 C: 1 0 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 3 2 2 1 2 3 4[A parenthesis: a quick finish A: 4 1 3 4 B: 1 2 3 4 5 C: 1 0 3 2 2 1 2 3 4 Walk through frequency array an place the appropriate number of each key in output array…A parenthesis: a quick finish A: 4 1 3 4 B: 1 1 2 3 4 5 C: 1 0 3 2 2 1 2 3 4A parenthesis: a quick finish A: 4 1 3 4 B: 1 1 2 3 4 5 C: 1 0 3 2 2 1 2 3 4A parenthesis: a quick finish A: 4 1 3 4 B: 1 3 3 1 2 3 4 5 C: 1 0 3 2 2 1 2 3 4A parenthesis: a quick finish A: 4 1 3 4 B: 1 3 3 4 4 1 2 3 4 5 C: 1 0 3 2 2 1 2 3 4 B is sorted! but it is not “stably sorted”…]Loop 2: count frequencies A: 4 1 3 4 B: 1 2 3 4 5 C: 1 0 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] …
View Full Document
Unlocking...