Question? Leave a message!




mergesort

mergesort
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Website URL
Comment
5. DIVIDE AND CONQUER I mergesort ‣ counting inversions ‣ closest pair of points ‣ randomized quicksort ‣ median and selection ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Oct 2, 2013 9:51 AMDivide-and-conquer paradigm Divide-and-conquer. 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 ). Divide-and-conquer: Θ(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 totally-ordered 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. Non-obvious 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 =. 8Divide-and-conquer 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: 3-2, 4-2 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 meta-searching 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 1-5, 2001, Hong Kong. ACM 1-58113-348-0/01/0005. 613 Copyright is held by the author/owner. WWW10, May 1-5, 2001, Hong Kong. ACM 1-58113-348-0/01/0005. 613Counting inversions: divide-and-conquer 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 5-4 6-3 9-3 9-7 count inversions (a, b) with a ∈ A and b ∈ B 1 5 4 8 10 2 6 9 3 7 4-2 4-3 5-2 5-3 8-2 8-3 8-6 8-7 10-2 10-3 10-6 10-7 10-9 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: divide-and-conquer algorithm implementation Input. List L. Output. Number of inversions in L and sorted list of elements L'. SORT-AND-COUNT (L) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ IF list L has one element RETURN (0, L). DIVIDE the list into two halves A and B. (r , A) ← SORT-AND-COUNT(A). A (r , B) ← SORT-AND-COUNT(B). B (r , L') ← MERGE-AND-COUNT(A, B). AB RETURN (r + r + r , L'). A B AB _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 18Counting inversions: divide-and-conquer algorithm analysis Proposition. The sort-and-count algorithm counts the number of inversions in a permutation of size n in O(n log n) time. Pf. The worst-case 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.4
sharer
Presentations
Free