Question? Leave a message!




mergesort

mergesort
5. DIVIDE AND CONQUER I mergesort ‣ counting inversions ‣ closest pair of points ‣ randomized quicksort ‣ median and selection ‣ Lecture slides by Kevin Wayne Copyright © 2005 PearsonAddison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on Oct 2, 2013 9:51 AMDivideandconquer paradigm Divideandconquer. Divide up problem into several subproblems. Solve each subproblem recursively. Combine solutions to subproblems into overall solution. Most common usage. Divide problem of size n into two subproblems of size n / 2 in linear time. Solve two subproblems recursively. Combine two solutions into overall solution in linear time. Consequence. 2 Brute force: Θ(n ). Divideandconquer: Θ(n log n). attributed to Julius Caesar 25. DIVIDE AND CONQUER mergesort ‣ counting inversions ‣ closest pair of points ‣ randomized quicksort ‣ median and selection ‣ SECTION 5.1Sorting problem Problem. Given a list of n elements from a totallyordered universe, rearrange them in ascending order. 4Sorting applications Obvious applications. Organize an MP3 library. Display Google PageRank results. List RSS news items in reverse chronological order. Some problems become easier once elements are sorted. Identify statistical outliers. Binary search in a database. Remove duplicates in a mailing list. Nonobvious applications. Convex hull. Closest pair of points. Interval scheduling / interval partitioning. Minimum spanning trees (Kruskal's algorithm). Scheduling to minimize maximum lateness or average completion time. ... 5Mergesort Recursively sort left half. Recursively sort right half. Merge two halves to make sorted whole. input A L G O R I T H M S sort left half A G L O R I T H M S sort right half A G L O R H I M S T merge results A G H I L M O R S T 6Merging Goal. Combine two sorted lists A and B into a sorted whole C. Scan A and B from left to right. Compare a and b . i j If a ≤ b , append a to C (no larger than any remaining element in B). i i j If a b , append b to C (smaller than every remaining element in A). i j j sorted list A sorted list B 3 7 10 18 2 11 17 23 a b i j 5 2 merge to form sorted list C 2 3 7 10 11 7A useful recurrence relation Def. T (n) = max number of compares to mergesort a list of size ≤ n. Note. T (n) is monotone nondecreasing. Mergesort recurrence. 0 if n = 1 T(n) ≤ T (⎡n / 2⎤ ) + T (⎣n / 2⎦ ) + n otherwise Solution. T (n) is O(n log n). 2 Assorted proofs. We describe several ways to prove this recurrence. Initially we assume n is a power of 2 and replace ≤ with =. 8Divideandconquer recurrence: proof by recursion tree Proposition. If T (n) satisfies the following recurrence, then T (n) = n log n. 2 assuming n 0 if n = 1 is a power of 2 T(n) = 2 T (n / 2) + n otherwise Pf 1. T (n) n = n T (n / 2) T (n / 2) 2 (n/2) = n 4 (n/4) = n T (n / 4) T (n / 4) T (n / 4) T (n / 4) log n 2 T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) = n 8 (n/8) ⋮ ⋮ T(n) = n lg n 9Proof by induction Proposition. If T (n) satisfies the following recurrence, then T (n) = n log n. 2 assuming n 0 if n = 1 is a power of 2 T(n) = 2 T (n / 2) + n otherwise Pf 2. by induction on n Base case: when n = 1, T(1) = 0. Inductive hypothesis: assume T(n) = n log n. 2 Goal: show that T(2n) = 2n log (2n). 2 T(2n) = 2 T(n) + 2n = 2 n log n + 2n 2 = 2 n (log (2n) – 1) + 2n 2 = 2 n log (2n). ▪ 2 10Analysis of mergesort recurrence Claim. If T(n) satisfies the following recurrence, then T(n) ≤ n ⎡log n⎤. 2 0 if n = 1 T(n) ≤ T (⎡n / 2⎤ ) + T (⎣n / 2⎦ ) + n otherwise Pf. by strong induction on n Base case: n = 1. Define n = ⎣n / 2⎦ and n = ⎡n / 2⎤. 1 2 Induction step: assume true for 1, 2, ... , n – 1. n =dn/2e 2 n =dn/2e n2 =dn/2e 2 l m l m l m dlog ne 2 n =dn/2e T(n) ≤ T(n ) + T(n ) + n 2  2dlog ne/2 1 2 dlog ne 2 2  2 /2  2 /2 l m dlog ne dlog 2ne ≤ n ⎡log n ⎤ + n ⎡log n ⎤ + n 2 1 2 1 2 2 2  2 /2 =2dlog ne/2 dlog ne 2 2 =2 /2 =2 /2 dlog ne ≤ n ⎡log n ⎤ + n ⎡log n ⎤ + n dlog n ed log ne 1 1 2 2 2 2 2 2 2 2 2 =2 /2 dlog n ed log ne 1 dlog n ed log ne 1 2 2 2 2 2 2 = n ⎡log n ⎤ + n log n d log ne 1 2 2 2 2 2 dlog n ed log ne 1 2 ≤ n (⎡log n⎤ – 1) + n 2 2 2 = n ⎡log n⎤. ▪ 2 115. DIVIDE AND CONQUER mergesort ‣ counting inversions ‣ closest pair of points ‣ randomized quicksort ‣ median and selection ‣ SECTION 5.3Counting inversions Music site tries to match your song preferences with others. You rank n songs. Music site consults database to find people with similar tastes. Similarity metric: number of inversions between two rankings. My rank: 1, 2, …, n. Your rank: a , a , …, a . 1 2 n Songs i and j are inverted if i j, but a a . i j A B C D E me 1 2 3 4 5 you 1 3 4 2 5 2 inversions: 32, 42 2 Brute force: check all Θ(n ) pairs. 13Counting inversions: applications Voting theory. Collaborative filtering. Measuring the "sortedness" of an array. Sensitivity analysis of Google's ranking function. Rank aggregation for metasearching on the Web. Nonparametric statistics (e.g., Kendall's tau distance). RankAggregationMethodsfortheWeb CynthiaDwork RaviKumar Moni Naor D. Sivakumar RankAggregationMethodsfortheWeb CynthiaDwork RaviKumar Moni Naor D. Sivakumar ABSTRACT ABSTRACT 1.1 Motivation 1. INTRODUCTION 14 1.1 Motivation 1. INTRODUCTION Copyright is held by the author/owner. WWW10, May 15, 2001, Hong Kong. ACM 1581133480/01/0005. 613 Copyright is held by the author/owner. WWW10, May 15, 2001, Hong Kong. ACM 1581133480/01/0005. 613Counting inversions: divideandconquer Divide: separate list into two halves A and B. Conquer: recursively count inversions in each list. Combine: count inversions (a, b) with a ∈ A and b ∈ B. Return sum of three counts. input 1 5 4 8 10 2 6 9 3 7 count inversions in left half A count inversions in right half B 1 5 4 8 10 2 6 9 3 7 54 63 93 97 count inversions (a, b) with a ∈ A and b ∈ B 1 5 4 8 10 2 6 9 3 7 42 43 52 53 82 83 86 87 102 103 106 107 109 output 1 + 3 + 13 = 17 15Counting inversions: how to combine two subproblems Q. How to count inversions (a, b) with a ∈ A and b ∈ B A. Easy if A and B are sorted Warmup algorithm. Sort A and B. For each element b ∈ B, binary search in A to find how elements in A are greater than b. list A list B 7 10 18 3 14 17 23 2 11 16 sort A sort B 3 7 10 14 18 2 11 16 17 23 binary search to count inversions (a, b) with a ∈ A and b ∈ B 3 7 10 14 18 2 11 16 17 23 5 2 1 1 0 16Counting inversions: how to combine two subproblems Count inversions (a, b) with a ∈ A and b ∈ B, assuming A and B are sorted. Scan A and B from left to right. Compare a and b . i j If a b , then a is not inverted with any element left in B. i j i If a b , then b is inverted with every element left in A. i j j Append smaller element to sorted list C. count inversions (a, b) with a ∈ A and b ∈ B 3 7 10 18 2 11 17 23 a b i j 5 2 merge to form sorted list C 2 3 7 10 11 17Counting inversions: divideandconquer algorithm implementation Input. List L. Output. Number of inversions in L and sorted list of elements L'. SORTANDCOUNT (L) IF list L has one element RETURN (0, L). DIVIDE the list into two halves A and B. (r , A) ← SORTANDCOUNT(A). A (r , B) ← SORTANDCOUNT(B). B (r , L') ← MERGEANDCOUNT(A, B). AB RETURN (r + r + r , L'). A B AB 18Counting inversions: divideandconquer algorithm analysis Proposition. The sortandcount algorithm counts the number of inversions in a permutation of size n in O(n log n) time. Pf. The worstcase running time T(n) satisfies the recurrence: Θ(1) if n = 1 T(n) = T (⎡n / 2⎤ ) + T (⎣n / 2⎦ ) + Θ(n) otherwise 195. DIVIDE AND CONQUER mergesort ‣ counting inversions ‣ closest pair of points ‣ randomized quicksort ‣ median and selection ‣ SECTION 5.4Closest pair of points Closest pair problem. Given n points in the plane, find a pair of points with the smallest Euclidean distance between them. Fundamental geometric primitive. Graphics, computer vision, geographic information systems, molecular modeling, air traffic control. Special case of nearest neighbor, Euclidean MST, Voronoi. fast closest pair inspired fast algorithms for these problems 21Closest pair of points Closest pair problem. Given n points in the plane, find a pair of points with the smallest Euclidean distance between them. 2 Brute force. Check all pairs with Θ(n ) distance calculations. 1d version. Easy O(n log n) algorithm if points are on a line. Nondegeneracy assumption. No two points have the same xcoordinate. 22Closest pair of points: first attempt Sorting solution. Sort by xcoordinate and consider nearby points. Sort by ycoordinate and consider nearby points. 23Closest pair of points: first attempt Sorting solution. Sort by xcoordinate and consider nearby points. Sort by ycoordinate and consider nearby points. 8 24Closest pair of points: second attempt Divide. Subdivide region into 4 quadrants. 25Closest pair of points: second attempt Divide. Subdivide region into 4 quadrants. Obstacle. Impossible to ensure n / 4 points in each piece. 26Closest pair of points: divideandconquer algorithm Divide: draw vertical line L so that n / 2 points on each side. Conquer: find closest pair in each side recursively. Combine: find closest pair with one point in each side. Return best of 3 solutions. 2 seems like Θ(N ) L 8 21 12 27How to find closest pair with one point in each side Find closest pair with one point in each side, assuming that distance δ. Observation: only need to consider points within δ of line L. L 21 δ = min(12, 21) 12 28 δHow to find closest pair with one point in each side Find closest pair with one point in each side, assuming that distance δ. Observation: only need to consider points within δ of line L. Sort points in 2δstrip by their ycoordinate. Only check distances of those within 11 positions in sorted list why 11 L 7 6 5 21 4 δ = min(12, 21) 12 3 2 1 29 δHow to find closest pair with one point in each side th Def. Let s be the point in the 2δstrip, with the i smallest ycoordinate. i Claim. If i – j ≥ 12, then the distance ⋮ between s and s is at least δ. i j 39 j 31 Pf. No two points lie in same ½ δby½ δ box. ½δ Two points at least 2 rows apart 2 rows have distance ≥ 2 (½ δ). ▪ 30 ½δ 29 ½δ 28 27 i Fact. Claim remains true if we replace 12 with 7. 26 25 ⋮ 30 δ δClosest pair of points: divideandconquer algorithm CLOSESTPAIR (p , p , …, p ) 1 2 n Compute separation line L such that half the points O(n log n) are on each side of the line. δ ← CLOSESTPAIR (points in left half). 1 2 T(n / 2) δ ← CLOSESTPAIR (points in right half). 2 δ ← min δ , δ . 1 2 Delete all points further than δ from line L. O(n) Sort remaining points by ycoordinate. O(n log n) Scan points in yorder and compare distance between each point and next 11 neighbors. If any of these O(n) distances is less than δ, update δ. RETURN δ. 31Closest pair of points: analysis Theorem. The divideandconquer algorithm for finding the closest pair of 2 points in the plane can be implemented in O(n log n) time. Θ(1) if n = 1 T(n) = T (⎡n / 2⎤ ) + T (⎣n / 2⎦ ) + O(n log n) otherwise 2 2 (x x ) + (y y ) 1 2 1 2 Lower bound. In quadratic decision tree model, any algorithm for closest pair (even in 1D) requires Ω(n log n) quadratic tests. 32Improved closest pair algorithm Q. How to improve to O(n log n) A. Yes. Don't sort points in strip from scratch each time. Each recursive returns two lists: all points sorted by xcoordinate, and all points sorted by ycoordinate. Sort by merging two presorted lists. Theorem. Shamos 1975 The divideandconquer algorithm for finding the closest pair of points in the plane can be implemented in O(n log n) time. Θ(1) if n = 1 Pf. T(n) = T (⎡n / 2⎤ ) + T (⎣n / 2⎦ ) + Θ(n) otherwise Note. See SECTION 13.7 for a randomized O(n) time algorithm. not subject to lower bound since it uses the floor function 335. DIVIDE AND CONQUER mergesort ‣ counting inversions ‣ closest pair of points ‣ randomized quicksort ‣ median and selection ‣ CHAPTER 7Randomized quicksort the array A 3way partition array so that: 7 6 12 3 11 8 9 1 4 10 2 Pivot element p is in place. p Smaller elements in left subarray L. the partitioned array A Equal elements in middle subarray M. 3 1 4 2 6 7 12 11 8 9 10 Larger elements in right subarray R. L M R Recur in both left and right subarrays. RANDOMIZEDQUICKSORT (A) IF list A has zero or one element RETURN. Pick pivot p ∈ A uniformly at random. 3way partitioning can be done inplace (L, M, R) ← PARTITION3WAY (A, a ). i (using n–1 compares) RANDOMIZEDQUICKSORT(L). RANDOMIZEDQUICKSORT(R). 35Analysis of randomized quicksort Proposition. The expected number of compares to quicksort an array of n distinct elements is O(n log n). Pf. Consider BST representation of partitioning elements. the original array of elements A 7 6 12 3 11 8 9 1 4 10 2 13 5 first partitioning element (chosen uniformly at random) first partitioning element in left subarray 9 3 11 1 8 10 13 12 2 4 6 5 7 36Analysis of randomized quicksort Proposition. The expected number of compares to quicksort an array of n distinct elements is O(n log n). Pf. Consider BST representation of partitioning elements. An element is compared with only its ancestors and descendants. 3 and 6 are compared first partitioning element (when 3 is partitioning element) (chosen uniformly at random) first partitioning element in left subarray 9 3 11 1 8 10 13 12 2 4 6 5 7 37Analysis of randomized quicksort Proposition. The expected number of compares to quicksort an array of n distinct elements is O(n log n). Pf. Consider BST representation of partitioning elements. An element is compared with only its ancestors and descendants. 2 and 8 are not compared first partitioning element (because 3 partitions them) (chosen uniformly at random) first partitioning element in left subarray 9 3 11 1 8 10 13 12 2 4 6 5 7 38Analysis of randomized quicksort Proposition. The expected number of compares to quicksort an array of n distinct elements is O(n log n). Pf. Consider BST representation of partitioning elements. An element is compared with only its ancestors and descendants. Pr a and a are compared = 2 / j i + 1. i j Pr2 and 8 compared = 2/7 first partitioning element (compared if either 2 or 8 are chosen (chosen uniformly at random) first partitioning as partition before 3, 4, 5, 6 or 7) element in left subarray 9 3 11 1 8 10 13 12 2 4 6 5 7 39Analysis of randomized quicksort Proposition. The expected number of compares to quicksort an array of n distinct elements is O(n log n). Pf. Consider BST representation of partitioning elements. An element is compared with only its ancestors and descendants. Pr a and a are compared = 2 / j i + 1. i j N N N N i+1 N N N N i+1 X X X X X N X N X N NX i+1 N N N N i+1 2 1 2 1 X X X X X X X X 2 1 2 1 Expected number of compares = =2 N N =2 N N i+1 X X =2X X =2 2 1 j i+1 j j i+1 j j i+1 j j i+1 j i=1 j=i+1 i=1 j=2 i=1 j=i+1 i=1 j=2 =2 i=1 j=i+1 i=1 j=2 i=1 j=i+1 i=1 j=2 j i+1 j N N i=1 j=i+1 i=1 j=2 X X N N 1 X 1 X 1 1  2N  2N N  2NX  2N j1 j all pairs i and j j j j=1 j=1  2N j=1 j=1 j Z Z N N Z Z j=1 N N 1 1 1 1 Z ⇠ 2N dx ⇠ 2N dx N ⇠ 2N dx ⇠ 2N dx 1 x x x=1 x=1 x x ⇠ 2N x=1 dx x=1 =2NlnN x =2NlnN x=1 =2NlnN =2NlnN =2NlnN Remark. Number of compares only decreases if equal elements. 405. DIVIDE AND CONQUER mergesort ‣ counting inversions ‣ closest pair of points ‣ randomized quicksort ‣ median and selection ‣ CHAPTER 9Median and selection problems th Selection. Given n elements from a totally ordered universe, find k smallest. Minimum: k = 1; maximum: k = n. Median: k = ⎣(n + 1) / 2⎦. O(n) compares for min or max. O(n log n) compares by sorting. O(n log k) compares with a binary heap. Applications. Order statistics; find the "top k"; bottleneck paths, … Q. Can we do it with O(n) compares A. Yes Selection is easier than sorting. 42Quickselect 3way partition array so that: Pivot element p is in place. Smaller elements in left subarray L. Equal elements in middle subarray M. Larger elements in right subarray R. th Recur in one subarray—the one containing the k smallest element. QUICKSELECT (A, k) Pick pivot p ∈ A uniformly at random. 3way partitioning can be done inplace (L, M, R) ← PARTITION3WAY (A, p). (using n–1 compares) IF k ≤ L RETURN QUICKSELECT (L, k). ELSE IF k L + M RETURN QUICKSELECT (R, k – L – M ) ELSE RETURN p. 43Quickselect analysis Intuition. Split candy bar uniformly ⇒ expected size of larger piece is ¾. T(n) ≤ T(¾ n) + n ⇒ T(n) ≤ 4 n th Def. T(n, k) = expected compares to select k smallest in an array of size ≤ n. Def. T(n) = max T(n, k). k Proposition. T(n) ≤ 4 n. can assume we always recur on largest subarray Pf. by strong induction on n since T(n) is monotonic and Assume true for 1, 2, …, n – 1. we are trying to get an upper bound T(n) satisfies the following recurrence: T(n) ≤ n + 2 / n T(n / 2) + … + T(n – 3) + T(n – 2) + T(n – 1) ≤ n + 2 / n 4 n / 2 + … + 4(n – 3) + 4(n – 2) + 4(n – 1) = n + 4 (3/4 n) = 4 n. ▪ tiny cheat: sum should start at T(⎣n/2⎦) 44Selection in worst case linear time Goal. Find pivot element p that divides list of n elements into two pieces so that each piece is guaranteed to have ≤ 7/10 n elements. Q. How to find approximate median in linear time A. Recursively compute median of sample of ≤ 2/10 n elements. Θ(1) if n = 1 T(n) = T (7/10 n) + T (2/10 n) + Θ(n) otherwise two subproblems of different sizes 45Choosing the pivot element Divide n elements into ⎣n / 5⎦ groups of 5 elements each (plus extra). 29 10 38 37 2 55 18 24 34 35 36 4 22 44 52 11 53 12 13 43 20 27 6 1 8 28 23 26 40 19 46 31 49 9 5 3 14 54 30 48 47 32 51 21 7 45 39 50 15 25 16 41 17 22 N = 54 46Choosing the pivot element Divide n elements into ⎣n / 5⎦ groups of 5 elements each (plus extra). Find median of each group (except extra). medians 29 10 38 38 37 2 55 18 18 24 34 35 35 36 4 22 44 52 11 53 12 13 43 43 20 27 6 1 8 28 28 23 23 26 40 40 19 19 46 31 31 49 9 5 3 14 54 30 48 47 32 51 21 7 45 39 50 15 15 25 16 41 17 22 N = 54 47Choosing the pivot element Divide n elements into ⎣n / 5⎦ groups of 5 elements each (plus extra). Find median of each group (except extra). Find median of ⎣n / 5⎦ medians recursively. Use medianofmedians as pivot element. medians median of medians 29 10 38 38 37 2 55 18 18 24 34 35 35 36 4 22 44 52 11 53 12 13 43 43 20 27 6 1 8 28 28 28 23 23 26 40 40 19 19 46 31 31 49 9 5 3 14 54 30 48 47 32 51 21 7 45 39 50 15 15 25 16 41 17 22 N = 54 48Medianofmedians selection algorithm MOMSELECT (A, k) n ← A . th IF n 50 RETURN k smallest of element of A via mergesort. Group A into ⎣n / 5⎦ groups of 5 elements each (plus extra). B ← median of each group of 5. median of medians p ← MOMSELECT(B, ⎣n / 10⎦) (L, M, R) ← PARTITION3WAY (A, p). IF k ≤ L RETURN MOMSELECT (L, k). ELSE IF k L + M RETURN MOMSELECT (R, k – L – M ) ELSE RETURN p. 49Analysis of medianofmedians selection algorithm At least half of 5element medians ≤ p. median of medians p 29 10 38 38 37 2 55 18 18 24 34 35 35 36 4 22 44 52 11 53 12 13 43 43 20 27 6 1 8 28 28 28 23 23 26 40 40 19 19 46 31 31 49 9 5 3 14 54 30 48 47 32 51 21 7 45 39 50 15 15 25 16 41 17 22 N = 54 50Analysis of medianofmedians selection algorithm At least half of 5element medians ≤ p. At least ⎣⎣n / 5⎦ / 2⎦ = ⎣n / 10⎦ medians ≤ p. median of medians p 29 10 38 37 2 55 18 18 24 34 35 36 4 22 44 52 11 53 12 13 43 20 27 6 1 8 28 28 28 23 23 26 40 19 19 46 31 49 9 5 3 14 54 30 48 47 32 51 21 7 45 39 50 15 15 25 16 41 17 22 N = 54 51Analysis of medianofmedians selection algorithm At least half of 5element medians ≤ p. At least ⎣⎣n / 5⎦ / 2⎦ = ⎣n / 10⎦ medians ≤ p. At least 3 ⎣n / 10⎦ elements ≤ p. median of medians p 29 10 10 38 37 2 55 18 18 24 34 35 36 4 22 22 44 52 11 11 53 12 12 13 13 43 20 27 6 1 1 8 28 28 28 23 23 26 40 19 19 46 31 49 9 9 5 3 3 14 14 54 30 48 47 32 51 21 7 45 39 50 15 15 25 16 16 41 17 22 N = 54 52Analysis of medianofmedians selection algorithm At least half of 5element medians ≥ p. median of medians p 29 10 38 38 37 2 55 18 18 24 34 35 35 36 4 22 44 52 11 53 12 13 43 43 20 27 6 1 8 28 28 28 23 23 26 40 40 19 19 46 31 31 49 9 5 3 14 54 30 48 47 32 51 21 7 45 39 50 15 15 25 16 41 17 22 53 N = 54Analysis of medianofmedians selection algorithm At least half of 5element medians ≥ p. Symmetrically, at least ⎣n / 10⎦ medians ≥ p. median of medians p 29 10 38 38 37 2 55 18 24 34 35 35 36 4 22 44 52 11 53 12 13 43 43 20 27 6 1 8 28 28 28 23 26 40 40 19 46 31 31 49 9 5 3 14 54 30 48 47 32 51 21 7 45 39 50 15 25 16 41 17 22 54 N = 54Analysis of medianofmedians selection algorithm At least half of 5element medians ≥ p. Symmetrically, at least ⎣n / 10⎦ medians ≥ p. At least 3 ⎣n / 10⎦ elements ≥ p. median of medians p 29 29 10 38 38 37 2 55 18 24 34 34 35 35 36 4 22 44 52 52 11 53 53 12 13 43 43 20 27 6 1 8 28 28 28 23 26 40 40 19 46 46 31 31 49 49 9 5 3 14 54 54 30 48 47 47 32 32 51 51 21 7 45 45 39 50 50 15 25 16 41 17 22 55 N = 54Medianofmedians selection algorithm recurrence Medianofmedians selection algorithm recurrence. Select called recursively with ⎣n / 5⎦ elements to compute MOM p. At least 3 ⎣n / 10⎦ elements ≤ p. At least 3 ⎣n / 10⎦ elements ≥ p. Select called recursively with at most n – 3 ⎣n / 10⎦ elements. Def. C(n) = max compares on an array of n elements. 11 C(n) ≤C( n /5 )+C (n− 3 n /10 ) + n ⎣ ⎦ ⎣ ⎦ 5 median of recursive computing median of 5 medians select (6 compares per group) partitioning (n compares) € Now, solve recurrence. Assume n is both a power of 5 and a power of 10 Assume C(n) is monotone nondecreasing 56Medianofmedians selection algorithm recurrence Analysis of selection algorithm recurrence. T(n) = max compares on an array of ≤ n elements. T(n) is monotone, but C(n) is not ⎧ 6n if n 50 ⎨ T(n) ≤ 11 T( n /5 ) + T(n − 3 n /10 ) + n otherwise ⎩ ⎣ ⎦ ⎣ ⎦ 5 Claim. T(n) ≤ 44 n. € Base case: T(n) ≤ 6 n for n 50 (mergesort). Inductive hypothesis: assume true for 1, 2, …, n – 1. Induction step: for n ≥ 50, we have: T(n) ≤ T(⎣n / 5⎦) + T(n – 3 ⎣n / 10⎦) + 11/5 n ≤ 44 (⎣n / 5⎦) + 44 (n – 3 ⎣n / 10⎦) + 11/5 n for n ≥ 50, 3 ⎣n / 10⎦ ≥ n / 4 ≤ 44 (n / 5) + 44 n – 44 (n / 4) + 11/5 n = 44 n. ▪ 57Lineartime selection postmortem Proposition. BlumFloydPrattRivestTarjan 1973 There exists a compare based selection algorithm whose worstcase running time is O(n). Time Bounds for Selection bY . Manuel Blum, Robert W. Floyd, Vaughan Watt, Ronald L. Rive, and Robert E. Tarjan Abstract L The number of comparisons required to select the ith smallest of n numbers is shown to be at most a linear function of n by analysis of i a new selection algorithm PICK. Specifically, no more than i 5.4305 n comparisons are ever required. This bound is improved for L extreme values of i , and a new lower bound on the requisite number of comparisons is also proved. L Theory. Optimized version of BFPRT: ≤ 5.4305 n compares. Best known upper bound DorZwick 1995: ≤ 2.95 n compares. L Best known lower bound DorZwick 1999: ≥ (2 + ε) n compares. 58 This work was supported by the National Science Foundation under grants GJ992 and GJ33170X. 1Lineartime selection postmortem Proposition. BlumFloydPrattRivestTarjan 1973 There exists a compare based selection algorithm whose worstcase running time is O(n). Time Bounds for Selection bY . Manuel Blum, Robert W. Floyd, Vaughan Watt, Ronald L. Rive, and Robert E. Tarjan Abstract L The number of comparisons required to select the ith smallest of n numbers is shown to be at most a linear function of n by analysis of i a new selection algorithm PICK. Specifically, no more than i 5.4305 n comparisons are ever required. This bound is improved for L extreme values of i , and a new lower bound on the requisite number of comparisons is also proved. L Practice. Constant and overhead (currently) too large to be useful. L Open. Practical selection algorithm whose worstcase running time is O(n). 59 This work was supported by the National Science Foundation under grants GJ992 and GJ33170X. 1
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.AlexanderTyler
User Type:
Teacher
Country:
India
Uploaded Date:
21-07-2017