Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 6 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 6 Prof. Erik Demaine
Order statistics Select the ith smallest of n elements( the element with rank i) i=l: minimum i-n.mimu i=L(n+1)2] or[(n+1)/2 median Naive algorithm: Sort and index ith element Worst-case running time=o(n Ig n)+O(1) o(n Ig n) using merge sort or heapsort(not quicksort) o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.2 Order statistics Select the ith smallest of n elements (the element with rank i). • i = 1: minimum; • i = n: maximum; • i = (n+1)/2 or (n+1)/2: median. Naive algorithm: Sort and index ith element. Worst-case running time = Θ(n lg n) + Θ(1) = Θ(n lg n), using merge sort or heapsort (not quicksort)
randomized divide-and conquer algorithm RAND-SELECT(A, p, g, i) bith smallest of.. g if p=g then return alp r<RAND-PARTITION(A, P, q k p+ >k=rank(A[rD if i=k then return a[rI if i<k then return RaNd-seleCt(A, p, r-1, i) else return RAND-SELECT(A, r+1, g, i-k) ≤A[ ≥A[r o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.3 Randomized divide-andconquer algorithm RAND-SELECT(A, p, q, i) ⊳ ith smallest of A[p . . q] if p = q then return A[p] r ← RAND-PARTITION(A, p, q) k ← r – p + 1 ⊳ k = rank(A[r]) if i = k then return A[r] if i < k then return RAND-SELECT(A, p, r – 1, i) else return RAND-SELECT(A, r + 1, q, i – k ) ≤≤AA[r] [r] ≥≥AA[r] [r] p q r k
Example Select the i=th smallest 61013583211i=7 pivot Partition 253681310111k=4 Select the 7-4=3rd smallest recursively o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6. 4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.4 Example pivot 66 1010 1313 55 88 33 22 1111 i = 7 k = 4 Select the 7 – 4 = 3rd smallest recursively. Select the i = 7th smallest: 22 55 33 66 88 1313 1010 1111 Partition:
Intuition for analysis (All our analyses today assume that all elements are distinct Lucky 7(n)=7(97/10)+e(m)nog091=n0=1 (n) case 3 Unlucky: 7(n)=7(n-1)+(n arithmetic series ⊙(n2) Worse than sorting o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.5 Intuition for analysis Lucky: 1 log10/ 91 0 n = n = CASE 3 T(n) = T(9n/10) + Θ(n) = Θ(n) Unlucky: T(n) = T(n – 1) + Θ(n) = Θ(n2) arithmetic series Worse than sorting! (All our analyses today assume that all elements are distinct.)