Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 5 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 5 Prof. Erik Demaine
How 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(nIgn) Is O(nlgn the best we can do? Decision trees can help us answer this question o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.2 How 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(n lg n). Is O(n lg n) the best we can do? Decision trees can help us answer this question
Decision-tree example Sort(a1,a2,…,an) 1:2 2:3 1:3 123 1:3 213 2:3 132 312 231 321 Each internal node is labeled i; i for i,jE(1,2, ..,n) The left subtree shows subsequent comparisons ifa s a The right subtree shows subsequent comparisons if a; 2a o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.3 Decision-tree example 1:21:2 2:3 2:3 123 123 1:31:3 132 132 312 312 1:3 1:3 213 213 2:32:3 231 231 321 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. Sort 〈a1, a2, …, an〉
Decision-tree example Sort(a1, a2, a3) 1:2 9≥4 =〈9,4,6) 2:3 1:3 123 1:3 213 2:3 132 312 231 321 Each internal node is labeled i; i for i,jE(1,2, ..,n) The left subtree shows subsequent comparisons ifa s a The right subtree shows subsequent comparisons if a; 2a o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.4 Decision-tree example 1:21:2 2:3 2:3 123 123 1:31:3 132 132 312 312 1:3 1:3 213 213 2:32:3 231 231 321 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 〉:
Decision-tree example Sort(a1, a2, a3) 1:2 =〈9,4,6) 2:3 1:3 9≥6 123 1:3 213 2:3 132 312 231 321 Each internal node is labeled i; i for i,jE(1,2, ..,n) The left subtree shows subsequent comparisons ifa s a The right subtree shows subsequent comparisons if a; 2a o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.5 Decision-tree example 1:21:2 2:3 2:3 123 123 1:31:3 132 132 312 312 1:3 1:3 213 213 2:32:3 231 231 321 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 〉: