6.006- Introduction to AlgorithmsLecture 8Prof. Piotr IndykMenu•Sorting!–Insertion Sort–Merge Sort•Recurrences–Master theoremThe problem of sortingInput: array A[1…n] of numbers.Output: permutation B[1…n] of A suchthat B[1] £ B[2] £ … £ B[n] .How can we do it efficiently ?e.g. A = [7, 2, 5, 5, 9.6] → B = [2, 5, 5, 7, 9.6]A:1 nInsertion sortINSERTION-SORT (A, n) ⊳ A[1 . . n]for j ← 2 to nj key sorted insert key A[j] into the (already sorted) sub-array A[1 .. j-1].Illustration of iteration j i new location of key by pairwise key-swaps down to its right positionExample of insertion sort 8 2 4 9 3 6Example of insertion sort 8 2 4 9 3 6Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6 2 3 4 6 8 9 doneRunning time? Θ(n2)e.g. when input is A = [n, n − 1, n − 2, . . . , 2, 1]Meet Merge SortMERGE-SORT A[1 . . n]1.If n = 1, done (nothing to sort).Key subroutine: MERGE divide and conquer2.Otherwise, recursively sort A[ 1 . . n/2 ] and A[ n/2+1 . . n ] .3.“Merge” the two sorted sub-arrays.201372121191Merging two sorted arraysMerging two sorted arrays 2013721211911Merging two sorted arrays 2013721211911 20137212119Merging two sorted arrays 2013721211911 201372121192Merging two sorted arrays 2013721211911 201372121192 2013712119Merging two sorted arrays 2013721211911 201372121192 20137121197Merging two sorted arrays 2013721211911 201372121192 20137121197 201312119Merging two sorted arrays 2013721211911 201372121192 20137121197 2013121199Merging two sorted arrays 2013721211911 201372121192 20137121197 2013121199 20131211Merging two sorted arrays 2013721211911 201372121192 20137121197 2013121199 2013121111Merging two sorted arrays 2013721211911 201372121192 20137121197 2013121199 2013121111 201312Merging two sorted arrays 2013721211911 201372121192 20137121197 2013121199 2013121111 20131212Merging two sorted arrays 2013721211911 201372121192 20137121197 2013121199 2013121111 20131212 Time = Q(n) to merge a total of n elements (linear time).Analyzing merge sortMERGE-SORT A[1 . . n]1.If n = 1, done.2.Recursively sort A[ 1 . . n/2 ] and A[ n/2+1 . . n ] .3.“Merge” the two sorted listsT(n)Q(1)2T(n/2)Q(n) T(n) =Q(1) if n = 1;2T(n/2) + Q(n) if n > 1. T(n) = ?Recurrence solvingSolve T(n) = 2T(n/2) + cn, where c > 0 is constant.Recursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant.T(n)Recursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. T(n/2)T(n/2)cnRecursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn T(n/4) T(n/4)T(n/4) T(n/4)cn/2cn/2Recursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/4 cn/4cn/4 cn/4cn/2cn/2Q(1)…Recursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/4 cn/4cn/4 cn/4cn/2cn/2Q(1)… h = lg nRecursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/4 cn/4cn/4 cn/4cn/2cn/2Q(1)…h = lg n cnRecursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/4 cn/4cn/4 cn/4cn/2cn/2Q(1)…h = lg n cncnRecursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/4 cn/4cn/4 cn/4cn/2cn/2Q(1)…h = lg n cncncn…Recursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/4 cn/4cn/4 cn/4cn/2cn/2Q(1)…h = lg n cncncn#leaves = nQ(n)…Recursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/4 cn/4cn/4 cn/4cn/2cn/2Q(1)…h = lg n cncncn#leaves = nQ(n) Total ?…Recursion treeSolve T(n) = 2T(n/2) + cn, where c > 0 is constant. cn cn/4 cn/4cn/4 cn/4cn/2cn/2Q(1)…h = lg n cncncn#leaves = nQ(n) Total = Q(n lg n)…The master method“One theorem to rule them all” (sort of)The master method applies to recurrences of the form T(n) = a T(n/b) + f (n) , where a ³ 1, b > 1, and f is positive.e.g. Mergesort: a=2, b=2, f(n)=O(n)e.g.2 Binary Search: a=1, b=2, f(n)=O(1)Basic Idea: Compare f (n) with nlogba.#subproblemssize of each subproblemtime to split into subproblems and combine resultsf (n/b) Idea of master theorem f (n/b)f (n/b)T (1)…Recursion tree:… f (n) af (n/b2)f (n/b2)f (n/b2)… a h = logbn f (n)a f (n/b)a2 f (n/b2) … #leaves = ah= alogbn= nlogbanlogbaT (1)T(n) = a T(n/b) + f (n)f (n/b) Idea of master theorem f (n/b)f (n/b)T (1)…Recursion tree:… f (n) af (n/b2)f (n/b2)f (n/b2)… a h = logbn f (n)a f (n/b)a2 f (n/b2) …nlogbaT (1)CASE 1: The weight increases geometrically from the root to the leaves. The leaves hold a constant fraction of the total weight. Q(nlogba)T(n) = a T(n/b) + f (n)f (n/b) Idea of master theorem f (n/b)f (n/b)T (1)…Recursion tree:… f (n) af (n/b2)f (n/b2)f (n/b2)… a h = logbn f (n)a f (n/b)a2 f (n/b2) …nlogbaT (1)CASE 2: (k = 0) The weight is approximately the same on each of the logbn levels. Q(nlogbalg n)T(n) = a T(n/b) + f (n)f (n/b) Idea of master theorem f (n/b)f (n/b)T (1)…Recursion tree:… f (n) af (n/b2)f (n/b2)f (n/b2)… a h = logbn f (n)a f (n/b)a2 f (n/b2) …nlogbaT (1)CASE 3: The weight decreases geometrically from the root to the leaves. The root holds a constant fraction of the total weight. Q( f (n))T(n) = a T(n/b) + f (n)Three common casesCompare f (n) with nlogba:1. f (n) = Θ(nlogba – e) for some constant e > 0.•f (n) grows polynomially slower than nlogba (by an ne factor).cost of level i = ai f (n/bi) = Q(nlogba-e ⋅bi e) so geometric increase of cost as we go deeper in the treeSolution: T(n) = Q(nlogba) .hence, leaf level cost dominates!Three common cases (cont.)Compare f (n) with nlogba:2. f (n) = Q(nlogba logkn) for some constant k ³ 0.•f (n) and nlogba grow at similar rates.Solution: T(n) = Q(nlogba logk+1n) .(cost of level i ) = ai f (n/bi) = Q(nlogba ⋅logk(n/bi)) so all levels have about the same costThree common cases (cont.)Compare f
View Full Document
Unlocking...