5.

D IVIDE A ND C ONQUER I

‣ mergesort
‣ counting inversions
‣ randomized quicksort
‣ median and selection
‣ closest pair of points

Lecture slides by Kevin Wayne


Copyright © 2005 Pearson-Addison Wesley

http://www.cs.princeton.edu/~wayne/kleinberg-tardos

Last updated on 3/12/18 9:21 AM

Divide-and-conquer paradigm

Divide-and-conquer.
Divide up problem into several subproblems (of the same kind).
Solve (conquer) 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. O(n) time
Solve (conquer) two subproblems recursively.
Combine two solutions into overall solution. O(n) time


Consequence.
Brute force: Θ(n2).
Divide-and-conquer: O(n log n).

attributed to Julius Caesar 2

 5. D IVIDE AND C ONQUER

‣ mergesort
‣ counting inversions
‣ randomized quicksort
‣ median and selection
‣ closest pair of points

SECTIONS 5.1–5.2
Sorting problem

Problem. Given a list L of n elements from a totally ordered universe,

rearrange them in ascending order.

4
Sorting 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.
Scheduling to minimize maximum lateness.
Minimum spanning trees (Kruskal’s algorithm).
... 5
Mergesort

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

6
Merging

Goal. Combine two sorted lists A and B into a sorted whole C.

Scan A and B from left to right.
Compare ai and bj.
If ai ≤ bj, append ai to C (no larger than any remaining element in B).
If ai > bj, append bj to C (smaller than every remaining element in A).

sorted list A sorted list B

3 7 10 ai 18 2 11 bj 20 23

merge to form sorted list C

2 3 7 10 11

7
Mergesort implementation

Input. List L of n elements from a totally ordered universe.

Output. The n elements in ascending order.

MERGE-SORT(L)
_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

IF (list L has one element)

RETURN L.


Divide the list into two halves A and B.

A ← MERGE-SORT(A). T (n / 2)

B ← MERGE-SORT(B). T (n / 2)

L ← MERGE(A, B). Θ(n)

RETURN L.
_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

8
A useful recurrence relation

Def. T (n) = max number of compares to mergesort a list of length n.



Recurrence.

 0 n=1

 T (n)
T ( n/2 ) + T ( n/2 ) + n n>1

 <latexit sha1_base64="G9BiiiqVnrc2NLAK0QbOMus1fE8=">AAACy3icbVFdb9MwFHUyPkr56sYjL1d0oCKkLJmQ2mkCTeKFJzSklk2qo8pxbjprjhPZDmoJfeSP8K/4NzhZJtGO++Kjc67P/UpKKYwNwz+ev3fv/oOHvUf9x0+ePns+2D/4ZopKc5zxQhb6MmEGpVA4s8JKvCw1sjyReJFcf2r0i++ojSjU1K5LjHO2VCITnFlHLQa/pyP1FugpUInN06cJLoWqufM0mz49DeENUIsrW4PI4FDBB4gOYQOUzsNgjHnscqYjKjNZFBrU0TFQ3eLG9Z1zbESOQnZaA28ltev98da7T1GlXROLwTAMwjbgLog6MCRdnC/2vQOaFrzKUVkumTHzKCxtXDNtBZfopqoMloxfsyXOHVQsRxPX7TI38NoxKWRumKxQFlr23x81y41Z54nLzJm9MrtaQ/5Pm1c2m8S1UGVlUfGbQlklwRbQXAZSoZFbuXaAcS1cr8CvmGbcuvttVWm9S+Rbk9SrSglepLjDSruymjVbjHZ3dhfMjoOTIPr6fng26dbZIy/JKzIiERmTM/KZnJMZ4V7PC7yxN/G/+Nb/4f+8SfW97s8LshX+r7/FTNWb</latexit>


 between ⎣n / 2⎦ and n − 1 compares



Solution. T (n) is O(n log2 n).




Assorted proofs. We describe several ways to solve this recurrence.

Initially we assume n is a power of 2 and replace ≤ with = in the recurrence.

9
 Divide-and-conquer recurrence: recursion tree

Proposition. If T (n) satisfies the following recurrence, then T (n) = n log2 n.

0 n=1 assuming n
T (n) = is a power of 2

<latexit sha1_base64="Z3k0jP42WP//6lnqi9e2pn3k2fw=">AAACo3icbVFNa9tAEF0pbZq4H3HSYy5DnYaUFkcyhaSElEAvPfSQFrsJWMKsViNnyWoldkfBrvAP7S0/pStHhdrpwC6PNzNvZt8mpZKWguC35288ebr5bGu78/zFy1c73d29n7aojMCRKFRhrhNuUUmNI5Kk8Lo0yPNE4VVy+6XJX92hsbLQQ5qXGOd8qmUmBSdHTbq/hkf6HURncN5cnSjBqdS1cIp20YnOAjiEiHBGNcgMDrQrCw9gAVE0DvonmMeuZgDRB3Ayx4NG6L2T0etdn/92dSLUaSs/6faCfrAMeAzCFvRYG5eTXW8vSgtR5ahJKG7tOAxKimtuSAqFbt/KYsnFLZ/i2EHNc7RxvTRpAW8dk0JWGHc0wZL9t6PmubXzPHGVOacbu55ryP/lxhVlp3EtdVkRavEwKKsUUAGN45BKg4LU3AEujHS7grjhhgty/7IyZaldolh5ST2rtBRFimusohkZ3rgYrnv2GIwG/U/98PvH3sVpa+cW22dv2BEL2Qm7YF/ZJRsxwe69TW/H6/qH/jf/hz98KPW9tuc1Wwk//gPFucbd</latexit>
2 T (n/2) + n n>1

T (n) n = n

T (n / 2) T (n / 2) 2 (n/2) = n

T (n / 4) T (n / 4) T (n / 4) T (n / 4) 4 (n/4) = n
log 2 n

T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) 8 (n/8) = n

⋮
⋮
T(n) = n log2 n
10
Proof by induction

Proposition. If T (n) satisfies the following recurrence, then T (n) = n log2 n.



0 n=1 assuming n

 is a power of 2
T (n) =


<latexit sha1_base64="Z3k0jP42WP//6lnqi9e2pn3k2fw=">AAACo3icbVFNa9tAEF0pbZq4H3HSYy5DnYaUFkcyhaSElEAvPfSQFrsJWMKsViNnyWoldkfBrvAP7S0/pStHhdrpwC6PNzNvZt8mpZKWguC35288ebr5bGu78/zFy1c73d29n7aojMCRKFRhrhNuUUmNI5Kk8Lo0yPNE4VVy+6XJX92hsbLQQ5qXGOd8qmUmBSdHTbq/hkf6HURncN5cnSjBqdS1cIp20YnOAjiEiHBGNcgMDrQrCw9gAVE0DvonmMeuZgDRB3Ayx4NG6L2T0etdn/92dSLUaSs/6faCfrAMeAzCFvRYG5eTXW8vSgtR5ahJKG7tOAxKimtuSAqFbt/KYsnFLZ/i2EHNc7RxvTRpAW8dk0JWGHc0wZL9t6PmubXzPHGVOacbu55ryP/lxhVlp3EtdVkRavEwKKsUUAGN45BKg4LU3AEujHS7grjhhgty/7IyZaldolh5ST2rtBRFimusohkZ3rgYrnv2GIwG/U/98PvH3sVpa+cW22dv2BEL2Qm7YF/ZJRsxwe69TW/H6/qH/jf/hz98KPW9tuc1Wwk//gPFucbd</latexit>
2 T (n/2) + n n>1



Pf. [ by induction on n ]
Base case: when n = 1, T(1) = 0 = n log2 n.
Inductive hypothesis: assume T(n) = n log2 n.
Goal: show that T(2n) = 2n log2 (2n).

recurrence

T(2n) = 2 T(n) + 2n

inductive hypothesis = 2 n log2 n + 2n

= 2 n (log2 (2n) – 1) + 2n

= 2 n log2 (2n). ▪
11
Divide-and-conquer: quiz 1

Which is the exact solution of the following recurrence?




0 n=1

 T (n) =

 <latexit sha1_base64="VRAYMk/LbRQG3UoGOQDaFFRdfHc=">AAACxXicbVFda9swFJW9ry77SrvHvVyWbqSMZXYYtCNsFPbSxw6StRCZIMvXqagsGUkuCSbsj+yP7d9Mdl1Y0t2nwzn389y0lMK6KPoThA8ePnr8ZO9p79nzFy9f9fcPflpdGY4zrqU2lymzKIXCmRNO4mVpkBWpxIv0+nujX9ygsUKrqVuXmBRsqUQuOHOeWvR/T4fqCL5Cj6a4FKrmvpfd9OgkgvdAHa5cDSKHQ+Vz4kPYAKXzaHSMReJzpkMqc6m1AfVpDNS0+Ajo5AOdQCNyFLLTGngnqY/xbvdvd917FFXWrbHoD6JR1AbcB3EHBqSL88V+cEAzzasCleOSWTuPo9IlNTNOcIn+rspiyfg1W+LcQ8UKtEnd2riBd57JIPfn5Fo5aNl/K2pWWLsuUp9ZMHdld7WG/J82r1x+ktRClZVDxW8H5ZUEp6H5CWTCIHdy7QHjRvhdgV8xw7jzn9ua0vYukW9dUq8qJbjOcIeVbuUMa1yMdz27D2bj0ZdR/OPz4PSks3OPvCFvyZDE5JickjNyTmaEB2EwDOJgHJ6FKnThzW1qGHQ1r8lWhL/+Aje6018=</latexit>
T ( n/2 ) + T ( n/2 ) + n 1 n>1

 no longer assuming n
is a power of 2

A. T(n) = n ⎣log2 n⎦

B. T(n) = n ⎡log2 n⎤

C. T(n) = n ⎣log2 n⎦ + 2⎣log2 n⎦ − 1

n
D. T(n) = n ⎡log2 n⎤ − 2⎡log2 n⎤ + 1 = log2 k
<latexit sha1_base64="OIDlLBbcsVZR990sJ0LjHkzac4E=">AAACWXicbVDLSgMxFE3HV62vVpdugkVwUcqMCCoiCG5cVrC20KlDJr2toZlkSO6IZehv+DVu9R8EP8b0sbDVC0lOzrk3N/fEqRQWff+r4K2srq1vFDdLW9s7u3vlyv6j1Znh0ORaatOOmQUpFDRRoIR2aoAlsYRWPLyd6K0XMFZo9YCjFLoJGyjRF5yho6KyH17Ra+q20GZJlA+vg/GTomEtrNFQchDSHXoQndIhDc3kHpWrft2fBv0Lgjmoknk0okphP+xpniWgkEtmbSfwU+zmzKDgEsalMLOQMj5kA+g4qFgCtptPRxvTY8f0aF8btxTSKfu7ImeJtaMkdpkJw2e7rE3I/7ROhv2Lbi5UmiEoPmvUzyRFTSc+0Z4wwFGOHGDcCPdXyp+ZYRydmwtdpm+nwBcmyV8zJbjuwRIr8RUNGzsXg2XP/oLmaf2y7t+fVW8u5nYWySE5IickIOfkhtyRBmkSTt7IO/kgn4Vvz/OKXmmW6hXmNQdkIbyDH4oEtJc=</latexit>
k=1
E. Not even Knuth knows.

12
Analysis of mergesort recurrence

Proposition. If T(n) satisfies the following recurrence, then T(n) ≤ n ⎡log2 n⎤.



 0 n=1
T (n)

 T ( n/2 ) + T ( n/2 ) + n n>1
<latexit sha1_base64="PlaAp4PYCkUIob8GuIy/Wl4iXIM=">AAACynicbVFdb9MwFHUyYKN8deORlys6UBGiJBOiQxNoEi+8IA2pZZPqqHKcm86aY0e2M7WK+sYf4Wfxb3CyTKId98VH51yf+5WWUlgXRX+CcOfe/Qe7ew97jx4/efqsv3/w0+rKcJxyLbW5SJlFKRROnXASL0qDrEglnqdXXxv9/BqNFVpN3KrEpGALJXLBmfPUvP97MlRvgJ4Aldg8PZriQqiae0+77tGTCF4Ddbh0NYgcDhV8hvgQ1kDpbDTGIvEpkyGVudTagHp/BNS0uDF96w0bkaOQndbAW0ltW3+5te5RVFnXw7w/iEZRG3AXxB0YkC7O5vvBAc00rwpUjktm7SyOSpfUzDjBJfqhKosl41dsgTMPFSvQJnW7yzW88kwGuR8m18pBy/77o2aFtasi9ZkFc5d2W2vI/2mzyuXHSS1UWTlU/KZQXklwGprDQCYMcidXHjBuhO8V+CUzjDt/vo0qrXeJfGOSelkpwXWGW6x0S2dYs8V4e2d3wfRo9GkU//gwOD3u1rlHXpCXZEhiMian5Bs5I1PCg93gXfAxGIffQxuuwvomNQy6P8/JRoS//gIlc9Vh</latexit>


 no longer assuming n
is a power of 2
Pf. [ by strong induction on n ]
Base case: n = 1.
Define n1 = ⎣n / 2⎦ and n2 = ⎡n / 2⎤ and note that n = n1 + n2.
Induction step: assume true for 1, 2, ... , n – 1.

T(n) ≤ T(n1) + T(n2) + n

n = dn/2e
n22 = dn/2e
l
inductive hypothesis ≤ n1 ⎡log2 n1⎤ + n2 ⎡log2 n2⎤ + n l dlog2 ne m m
n
2 =2 dn/2e
2dlog 2 ne /
/ 2
2 m
l
≤ n1 ⎡log2 n2⎤ + n2 ⎡log2 n2⎤ + n dlog dlog
ne 2 ne / 2
= 2dlog222 ne /
=2 /22
= n ⎡log2 n2⎤ + n dlog n22 ee 
dlog22 n  dlog 2 ne
= 2dlog
dlog ne 1
2 ne /
12
2
≤ n (⎡log2 n⎤ – 1) + n log2 n2  dlog2 ne 1
dlog2 n2 e  dlog2 ne 1
= n ⎡log2 n⎤. ▪ an integer
Digression: sorting lower bound

Challenge. How to prove a lower bound for all conceivable algorithms?



Model of computation. Comparison trees.
Can access the elements only through pairwise comparisons.
All other operations (control, data movement, etc.) are free.


Cost model. Number of compares.


Q. Realistic model?
A1. Yes. Java, Python, C++, …
A2. Yes. Mergesort, insertion sort, quicksort, heapsort, …
A3. No. Bucket sort, radix sorts, …



Comparable[] a = ...;
... can access elements only
Arrays.sort(a); via calls to compareTo()

14
Comparison tree (for 3 distinct keys a, b, and c)

a<b
height of pruned tree =

yes no worst-case number

of compares
code between compares

(e.g., sequence of exchanges)

b<c a<c

yes no yes no

abc a<c bac b<c

yes no yes no

acb cab bca cba

each reachable leaf corresponds to one (and only one) ordering;

exactly one reachable leaf for each possible ordering 15
Sorting lower bound

Theorem. Any deterministic compare-based sorting algorithm must make

Ω(n log n) compares in the worst-case.


Pf. [ information theoretic ]
Assume array consists of n distinct values a1 through an.
Worst-case number of compares = height h of pruned comparison tree.
Binary tree of height h has ≤ 2h leaves.
n! different orderings ⇒ n! reachable leaves.

n! leaves ≤ 2h leaves

16
Sorting lower bound

Theorem. Any deterministic compare-based sorting algorithm must make

Ω(n log n) compares in the worst-case.


Pf. [ information theoretic ]
Assume array consists of n distinct values a1 through an.
Worst-case number of compares = height h of pruned comparison tree.
Binary tree of height h has ≤ 2h leaves.
n! different orderings ⇒ n! reachable leaves.




 2h ≥ # leaves ≥ n !

 ⇒ h ≥ log2 (n!)


≥ n log2 n − n / ln 2 ▪




Stirling’s formula



Note. Lower bound can be extended to include randomized algorithms. 17
SHUFFLING A LINKED LIST

Problem. Given a singly linked list, rearrange its nodes uniformly at random.
Assumption. Access to a perfect random-number generator.
all n! permutations

 equally likely

Performance. O(n log n) time, O(log n) extra space.

L
input

2♣ 3♣ 4♣ 5♣ 6♣ 7♣ null

L
shuffled

5♣ 6♣ 2♣ 7♣ 3♣ 4♣ null

18
 5. D IVIDE AND C ONQUER

‣ mergesort
‣ counting inversions
‣ randomized quicksort
‣ median and selection
‣ closest pair of points

SECTION 5.3
Counting 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: a1, a2, …, an.
Songs i and j are inverted if i < j, but ai > aj.




A B C D E


me 1 2 3 4 5



 you 1 3 4 2 5


 2 inversions: 3-2, 4-2



Brute force: check all Θ(n2) pairs.

20
Counting 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).

Rank Aggregation Methods for the Web

Cynthia Dwork Ravi Kumar Moni Naor D. Sivakumar

Rank Aggregation Methods for the Web

Cynthia Dwork Ravi Kumar Moni Naor D. Sivakumar

ABSTRACT

ABSTRACT

1.1 Motivation

1. INTRODUCTION
21
1.1 Motivation
Counting 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 22
Counting 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 20 23 2 11 16

sort A sort B

3 7 10 14 18 2 11 16 20 23

binary search to count inversions (a, b) with a ∈ A and b ∈ B

3 7 10 14 18 2 11 16 20 23

5 2 1 0 0
23
Counting 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 ai and bj.
If ai < bj, then ai is not inverted with any element left in B.
If ai > bj, then bj is inverted with every element left in A.
Append smaller element to sorted list C.

count inversions (a, b) with a ∈ A and b ∈ B

3 7 10 ai 18 2 11 bj 20 23

5 2

merge to form sorted list C

2 3 7 10 11

24
Counting inversions: divide-and-conquer algorithm implementation

Input. List L.
Output. Number of inversions in L and L in sorted order.

SORT-AND-COUNT(L)
_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

IF (list L has one element)

RETURN (0, L).


Divide the list into two halves A and B.
(rA, A) ← SORT-AND-COUNT(A). T (n / 2)

(rB, B) ← SORT-AND-COUNT(B). T (n / 2)

(rAB, L) ← MERGE-AND-COUNT(A, B). Θ(n)



RETURN (rA + rB + rAB, L).
_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

25
Counting 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) n=1
T (n) =
<latexit sha1_base64="3pXfe56Q7VvCgldQ8ZGmWT26i7U=">AAAC2HicbVHLattAFB0pfaTuy0npqpuhTotDwZFCIQmmJdAWukzBbgIaYUbjK3vIaCRmroqN8KKr0m1/pN/Tv+lIUaC2exfD4Zw799xHUihpMQj+eP7Onbv37u8+6Dx89PjJ0+7e/lebl0bAWOQqN1cJt6CkhjFKVHBVGOBZouAyuf5Q65ffwFiZ6xEuC4gzPtMylYKjoybd36O+PqRsSN/VT4clMJO6Eq6iXXXYkI3mgLwfHtLXlCEssKIypQfapYcHdEUZiwYnkMUuddRnKlV5bqg+OqbMNLgu/cYVrkUBUrVaDW+l1kJvWby/tegw0NO2p0m3FwyCJug2CFvQI21cTPa8fTbNRZmBRqG4tVEYFBhX3KAUCtyQpYWCi2s+g8hBzTOwcdVsdkVfOWZKUzdUmmukDfvvj4pn1i6zxGVmHOd2U6vJ/2lRielpXEldlAha3BilpaKY0/pMdCoNCFRLB7gw0vVKxZwbLtAdc82lqV2AWJukWpRainwKG6zCBRpebzHc3Nk2GB8Pzgbhl7e989N2nbvkBXlJ+iQkJ+ScfCYXZEyE99wbeh+9T37kf/d/+D9vUn2v/fOMrIX/6y+lidpE</latexit>
T ( n/2 ) + T ( n/2 ) + (n) n>1

26
 5. D IVIDE AND C ONQUER

‣ mergesort
‣ counting inversions
‣ randomized quicksort
‣ median and selection
‣ closest pair of points

SECTION 7.1–7.3
3-WAY PARTITIONING

Goal. Given an array A and pivot element p, partition array so that:

Smaller elements in left subarray L.
Equal elements in middle subarray M.
Larger elements in right subarray R.

Challenge. O(n) time and O(1) space.

the array A

7 6 12 3 11 8 9 1 4 10 2

the partitioned array A

3 1 4 2 6 7 12 11 8 9 10

L M R
28
Randomized quicksort

Pick a random pivot element p ∈ A.

3-way partition the array into L, M, and R.
Recursively sort both L and R.

the array A 7 6 12 3 11 8 9 1 4 10 2

partition A 3 1 4 2 6 7 12 11 8 9 10

sort L 1 2 3 4 6 7 12 11 8 9 10

sort R 1 2 3 4 6 7 8 9 10 11 12

the sorted array A 1 2 3 4 6 7 8 9 10 11 12

29
Randomized quicksort

Pick a random pivot element p ∈ A.

3-way partition the array into L, M, and R.
Recursively sort both L and R.

RANDOMIZED-QUICKSORT(A)
_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

IF (array A has zero or one element)

RETURN.
Pick pivot p ∈ A uniformly at random.
(L, M, R) ← PARTITION-3-WAY(A, p). Θ(n)

RANDOMIZED-QUICKSORT(L). T (i) new analysis required

(i is a random variable—depends on p)
RANDOMIZED-QUICKSORT(R). T (n − i − 1)
_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

30
Analysis of randomized quicksort

Proposition. The expected number of compares to quicksort an array


of n distinct elements a1 < a2 < < an is O(n log n).


Pf. Consider BST representation of pivot elements.

the original array of elements A

a7 a6 a12 a3 a11 a8 a9 a1 a4 a10 a2 a13 a5

first pivot
(chosen uniformly at random)
first pivot in
left subarray
a9

a3 a11

a1 a8 a10 a13

a2 a4 a12

a6

a5 a7
31
Analysis of randomized quicksort

Proposition. The expected number of compares to quicksort an array


of n distinct elements a1 < a2 < < an is O(n log n).

Pf. Consider BST representation of pivot elements.

ai and aj are compared once iff one is an ancestor of the other.

a3 and a6 are compared


first pivot
(when a3 is pivot)
(chosen uniformly at random)
first pivot in
left subarray
a9

a3 a11

a1 a8 a10 a13

a2 a4 a12

a6

a5 a7
32
Analysis of randomized quicksort

Proposition. The expected number of compares to quicksort an array


of n distinct elements a1 < a2 < < an is O(n log n).

Pf. Consider BST representation of pivot elements.

ai and aj are compared once iff one is an ancestor of the other.

a2 and a8 are not compared

first pivot
(because a3 partitions them)
(chosen uniformly at random)
first pivot in
left subarray
a9

a3 a11

a1 a8 a10 a13

a2 a4 a12

a6

a5 a7
33
Divide-and-conquer: quiz 2

Given an array of n ≥ 8 distinct elements a1 < a2 < < an, what is the
probability that a7 and a8 are compared during randomized quicksort?


A. 0

B. 1/n

C. 2/n
if two elements are adjacent,
D. 1 one must be an ancestor of the other

a9

a3 a11

a1 a8 a10 a13

a2 a4 a12

a6

a5 a7
34
Divide-and-conquer: quiz 3

Given an array of n ≥ 2 distinct elements a1 < a2 < < an, what is the
probability that a1 and an are compared during randomized quicksort?


A. 0

B. 1/n
a1 and an are compared
C. 2/n iff first pivot is either a1 or an

D. 1

a9

a3 a11

a1 a8 a10 a13

a2 a4 a12

a6

a5 a7
35
Analysis of randomized quicksort

Proposition. The expected number of compares to quicksort an array of n

distinct elements a1 < a2 < < an is O(n log n).

Pf. Consider BST representation of pivot elements.

ai and aj are compared once iff one is an ancestor of the other.
Pr [ ai and aj are compared ] = 2 / ( j - i + 1), where i < j.

Pr[a2 and a8 compared] = 2/7

compared iff either a2 or a8 is chosen

as pivot before any of { a3, a4, a5, a6, a7}
a9

a3 a11

a1 a8 a10 a13

a2 a4 a12

a6

a5 a7
36
Analysis of randomized quicksort

Proposition. The expected number of compares to quicksort an array of n

distinct elements a1 < a2 < < an is O(n log n).


Pf. Consider BST representation of pivot elements.
ai and aj are compared once iff one is an ancestor of the other.
Pr [ ai and aj are compared ] = 2 / ( j - i + 1), where i < j.

n
n n
n n
n n n i+1
i+1
n n 2 n n i+1 1
Expected number of compares = n n 2 = 2 n n i+1 1
j i2+ 1 = 2 j1


i=1
i=1 j=i+1
j=i+1
i=1 j=i+1
j i 1 = 2 i=1 j=2 j
i=1
i=1 j=2
j=2
i=1 j=i+1
j i 1 i=1n j=2 j
n
n 1

 2n n 1
all pairs i and j 2n j1

 2n j=1 j
j=1
j=1
n j

 2n (lnnn +1 1)
j=1
1 dx
<latexit sha1_base64="TSQczVbIEUgfpzVbrGceKD3sGfA=">AAADBHicjZFNb9NAEIbXLh8lfKXlyGVEBCoqRLZViVZRpSIuHItEaKVsiNabcbrteu3urlEjy2d+DSfElf+B+DOs7YCSFCFGsvzuMzPv2jNxLoWxQfDD8zdu3Lx1e/NO5+69+w8edre2P5is0ByHPJOZPo2ZQSkUDq2wEk9zjSyNJZ7EF2/q/Mkn1EZk6r2d5zhO2UyJRHBmHZp0f1JTpJNSHIbVx1JVQF9AS87hEMSuo6phiWa8jKry/GUN4RnQAR24kuYVAfzLJqpZ2/fHKnRW7kg7v62oxFZApJZ6l/z+p28AO1QqULAL4fNJtxf0gybguggXokcWcTzZ8rbpNONFispyyYwZhUFuxyXTVnCJVYcWBnPGL9gMR04qlqIZl80WKnjqyBSSTLtHWWjockfJUmPmaewqU2bPzHquhn/LjQqb7I9LofLCouLtRUkhwWZQrxSmQiO3cu4E41q4bwV+xty0rFv8yi2Nd4585U/Kq0IJnk1xjUp7ZTWr3BTD9ZldF8Oof9AP3+31jvYX49wkj8kTskNC8oockbfkmAwJ9157My/3Lv3P/hf/q/+tLfW9Rc8jshL+91/5zen5</latexit>

2n
2n (ln
2n n+x dx
1) ▪

 <latexit sha1_base64="GjZqOMHt99byYg9EpBf0uRtS8Xc=">AAADBHicjZFdb9MwFIad8DXKx7pxyc0RFWhotIojJDZVk4a44XJIlE2qS+W4TufNcYLtTKusXO/X7Apxy/9A/BmctIi2Q4gjRXn9nHNeJ+ckhRTGRtGPILx1+87dexv3Ww8ePnq82d7a/mTyUjM+YLnM9UlCDZdC8YEVVvKTQnOaJZIfJ+fv6vzxBddG5OqjnRV8lNGpEqlg1Ho0bv8kpszGThzg6rNTFZBXMCdncABi11PVsFRT5uLKnXVFF1fwAkif9H1J84oB/mUT16xbm/2xwt7KH0nrtxWRfC4gVku9S37/09eHHSIVKNgF/HLc7kS9qAm4KfBCdNAijsZbwTaZ5KzMuLJMUmOGOCrsyFFtBZO8apHS8IKyczrlQy8VzbgZuWYLFTz3ZAJprv2jLDR0ucPRzJhZlvjKjNpTs56r4d9yw9KmeyMnVFFartj8orSUYHOoVwoToTmzcuYFZVr4bwV2Sv20rF/8yi2Nd8HZyp+4y1IJlk/4GpX20mpa+Sni9ZndFIO4t9/DH153DvcW49xAT9EztIMweoMO0Xt0hAaIBW+DaVAEX8Kr8Dr8Gn6bl4bBoucJWonw+y/+pen7</latexit>
x=1
x=1 x
= 2n ln n

 = 2n ln n
harmonic sum




Remark. Number of compares only decreases if equal elements. 37
 Tony Hoare
n u m b e r ) . 9.9 X 10 45 is u s e d to r e p r e s e n t i n f i n i t y . I m a g i n a r y
v a l u e s of x m a y n o t be n e g a t i v e a n d reM v a l u e s of x m a y n o t be
conunent I a n d J are o u t p u t v a r i a b l e s , a n d A is t h e a r r a y ( w i t h
s u b s c r i p t b o u n d s M : N ) w h i c h is o p e r a t e d u p o n b y t h i s p r o c e d u r e .
s m a l l e r t h a n 1. P a r t i t i o n t a k e s t h e v a l u e X of a r a n d o m e l e m e n t of t h e a r r a y A,
V a l u e s of Qd~'(x) m a y be c a l c u l a t e d e a s i l y by h y p e r g e o m e t r i c a n d r e a r r a n g e s t h e v a l u e s of t h e e l e m e n t s of t h e a r r a y in s u c h a
series if x is n o t t o o s m a l l n o r (n - m ) t o o large. Q~m(x) c a n be w a y t h a t t h e r e e x i s t i n t e g e r s I a n d J w i t h t h e following p r o p e r t i e s :
c o m p u t e d f r o m a n a p p r o p r i a t e set of v a l u e s of Pnm(X) if X is n e a r M _-< J < I =< N p r o v i d e d M < N

Invented quicksort to translate Russian into English.

1.0 or ix is n e a r 0. L o s s of s i g n i f i c a n t d i g i t s o c c u r s for x as s m a l l as A[R] =< X f o r M =< R _-< J
1.1 if n is l a r g e r t h a n 10. L o s s of s i g n i f i c a n t d i g i t s is a m a j o r diffi- A[R] = X f o r J < R < I
c u l t y in u s i n g finite p o l y n o m i M r e p r e s e n t a t i o n s also if n is l a r g e r A[R] ~ X f o r I =< R ~ N
t h a n m . H o w e v e r , Q L E G h a s b e e n t e s t e d in r e g i o n s of x a n d n The procedure uses an integer procedure random (M,N) which

procedure
[ but couldn’t explain his algorithm or implement it! ]
b o t h large a n d small;
Q L E G ( m , n m a x , x, ri, R, Q); v a l u e In, n m a x , x, ri;
chooses equiprobably a random integer F between M and N, and
also a p r o c e d u r e e x c h a n g e , w h i c h e x c h a n g e s t h e v a l u e s of its t w o
r e a l In, m n a x , x, ri; r e a l a r r a y R , Q; parameters ;
begin
Learned Algol 60 (and recursion).
r e a l t, i, n, q0, s;
n : = 20;
begin real X; integer F;
F : = r a n d o m ( M , N ) ; X : = A[F];
i f n m a x > 13 t h e n I:=M; J:=N;

Implemented quicksort.
n := nmax +7;
i f ri = 0 t h e n
up: for I : = I s t e p 1 u n t i l N d o
i f X < A [I] t h e n g o to d o w n ;
begin ifm = 0then I:=N;
Q[0] : = 0.5 X 10g((x + 1 ) / ( x - 1)) down: f o r J : = J s t e p --1 u n t i l M d o
else if A[J]<X then go to change;
begin t : = - - 1 . 0 / s q r t ( x X x - - 1); J:=M;
q0 : = 0; c h a n g e : i f I < J t h e n b e g i n e x c h a n g e (A[IL A[J]); Tony Hoare

Q[O] : = t ; I := I+ 1;J:= J - 1;
for i : = 1 step 1 until m do g o to u p 1980 Turing Award
begin s := (x+x)X(i-1)Xt end 2: b e g i n
4
×Q[0]+ (3i-i×i-2)×q0; else i f [ < F t h e n b e g i n e x c h a n g e (A[IL A[F]) i i f c >= 0 t h e n
q0 : = Q[0]; I:=I+l 3:begin
Q[0] : = s e n d e n d ; end e:= aXe;f := bXd;goto8
if x = 1 then else i f F < J t l l e n b e g i n e x c h a n g e (A[F], A[J]) ; end 3 ;
Q[0] : = 9.9 I" 45; J:=J-1 e:=bXc;
R [ n + 1] : = x - s q r t ( x X x - 1); end ; ifd ~ 0then
for i : = n s t e p --1 u n t i l 1 d o end partition 4: begin
R[i] : = (i + m ) / ( ( i + i + 1) X x f:=bXd; goto8
+(m-i- 1) X R [ i + l ] ) ; e n d 4;
ALGORITHM 61
g o to t h e e n d ; f:=aXd; goto8
if m = 0 then ALGORITHM
PROCEDURES 64F O R R A N G E ARITHMETIC 5: e n d 2;
b e g i n i f x < 0.5 t b e n QUICKSORT
ALLAN GIBB* ifb > 0 then
Q[0] : = a r c t a n ( x ) - 1.5707963 e l s e U n iA.
C. i t y HOARE
v e r sR. of A l b e r t a , C a l g a r y , A l b e r t a , C a n a d a 6: b e g i n
Q[0] : = - a r e t a n ( 1 / x ) e n d e l s e if d > 0 then
Elliott
b e g i n Brothers Ltd., Borehamwood, Hertfordshire, Eng.
begin t : = 1 / s q r t ( x X x + 1); begin
p r o c e d u r e R A N G E S U M (a, b, c, d, e, f);
q0 : = 0; procedure quicksort (A,M,N); value M,N; e : = M I N ( a X d, b X c);
real a , b , c , d , e , f ;
q[0] := t; a r r a y A; i n t e g e r M , N ; f : = M A X ( a X c , b X d); go t o 8
c o m m e n t The term "range n u m b e r " was used by P. S. Dwyer,
for i : = 2 step 1 until m do comment Q u i c k s o r t is a v e r y f a s t a n d c o n v e n i e n t m e t h o d of e n d 6;
b e g i n s : = (x + x) X (i -- 1) X t X Q[0I
Linear Computations (Wiley, 1951). Machine procedures for
s o r t i n g a n a r r a y in t h e r a n d o m - a c c e s s s t o r e of a c o m p u t e r . T h e e : = b X c; f : = a X c; go t o 8
range arithmetic were developed about 1958 by Ramon Moore,
+(3i+iX i -- 2) × q0; e n t i r e c o n t e n t s of t h e s t o r e m a y be s o r t e d , since no e x t r a s p a c e is e n d 5;
"Automatic Error Analysis in Digital C o m p u t a t i o n , " LMSD
qO : = Q[0]; r e q u i r e d . T h e a v e r a g e n u m b e r of c o m p a r i s o n s m a d e is 2 ( M - - N ) In f:=aXc;
Report 48421, 28 Jan. 1959, Lockheed Missiles and Space Divi-
Q[0] := s e n d e n d ; ( N - - M ) , a n d t h e a v e r a g e n m n b e r of e x c h a n g e s is one s i x t h t h i s i f d _-<O t h e n
sion, Palo Alto, California, 59 pp. If a _< x -< b and c ~ y ~ d,
R[n + 1] : = x - s q r t ( x × x + 1); a m o u n t . S u i t a b l e r e f i n e m e n t s of t h i s m e t h o d will be d e s i r a b l e for 7: b e g i n
then R A N G E S U M yields an interval [e, f] such t h a t e =< (x + y)
for i := n step - 1 until 1 do its i m p l e m e n t a t i o n on a n y a c t u a l c o m p u t e r ; e:=bXd; goto8
f. Because of machine operation (truncation or rounding) the
R[i] : = (i + m ) / ( ( i -- m + 1) × R[i + 1] begin i n t e g e r 1,J ; end 7 ;
machine sums a -4- c and b -4- d may not provide safe end-points
--(i+i+ 1) X x); if M < N then begin partition (A,M,N,I,J); e:=aXd;
of the output interval. Thus R A N G E S U M requires a non-local
for i : = 1 step 2 until nmax do quicksort (A,M,J) ; 8: e : = A D J U S T P R O D (e, - 1 ) ;
real procedure A D J U S T S U M which will compensate for the
Rill : = -- Rill; q u i c k s o r t (A, I, N ) f := A D J U S T P R O D (f, 1)
machine arithmetic. The body of A D J U S T S U M will be de-
the: for i : = 1 step 1 until nnmx do end end RANGEMPY;
pendent upon the type of machine for which it is written and so
Q[i] : = Q[i - 1] X R[i] end quieksort p r o c e d u r e R A N G E D V D (a, b, c, d, e, f) ;
is not given here. (An example, however, appears below.) I t
end QLEG; real a, b, c, d, e, f;
is assumed t h a t A D J U S T S U M has as parameters real v and w,
c o m m e n t If the range divisor includes zero the program
* T h i s p r o c e d u r e w a s d e v e l o p e d in p a r t u n d e r t h e s p o n s o r s h i p and integer i, and is accompanied by a non-local real procedure
exists to a non-local label " z e r o d v s r " . R A N G E D V D assumes a
of t h e A i r F o r c e C a m b r i d g e R e s e a r c h C e n t e r .
Communications of the ACM (July 1961)
C O R R E C T I O N 65
ALGORITHM which gives an upper bound to the magnitude
of the error involved in the machine representation of a number.
non-local real procedure A D J U S T Q U O T which is analogous
FINDThe output A D J U S T S U M provides the left end-point of the
(possibly identical) to A D J U S T P R O D ; 38
C.output A. R.intervalHOARE begin
of R A N G E S U M when A D J U S T S U M is called
NUTS AND BOLTS

Problem. A disorganized carpenter has a mixed pile of n nuts and n bolts.

The goal is to find the corresponding pairs of nuts and bolts.
Each nut fits exactly one bolt and each bolt fits exactly one nut.
By fitting a nut and a bolt together, the carpenter can see which one is
bigger (but cannot directly compare either two nuts or two bolts).
















Brute-force solution. Compare each bolt to each nut—Θ (n 2) compares.
Challenge. Design an algorithm that makes O(n log n) compares.
39
 5. D IVIDE AND C ONQUER

‣ mergesort
‣ counting inversions
‣ randomized quicksort
‣ median and selection
‣ closest pair of points

SECTION 9.3
Median and selection problems

Selection. Given n elements from a totally ordered universe, find kth 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.
 max heap with k smallest

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.

43
Randomized quickselect

Pick a random pivot element p ∈ A.

3-way partition the array into L, M, and R.
Recur in one subarray—the one containing the kth smallest element.

QUICK-SELECT(A, k)
_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Pick pivot p ∈ A uniformly at random.

(L, M, R) ← PARTITION-3-WAY(A, p). Θ(n)

IF (k ≤ | L |) RETURN QUICK-SELECT(L, k). T (i)

ELSE IF (k > | L | + | M |) RETURN QUICK-SELECT(R, k – | L | – | M |) T (n − i − 1)

ELSE IF (k = | L |) RETURN p.
_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

44
Randomized quickselect analysis

Intuition. Split candy bar uniformly ⇒ expected size of larger piece is ¾.


 T(n) ≤ T(3 n / 4) + n ⇒ T(n) ≤ 4 n


not rigorous: can’t assume
E[T(i)] ≤ T(E[i])

Def. T(n, k) = expected # compares to select kth smallest in array of length ≤ n.

Def. T(n) = maxk T(n, k).


Proposition. T(n) ≤ 4 n.
Pf. [ by strong induction on n ] can assume we always recur of
larger of two subarrays since T(n)
Assume true for 1, 2, …, n – 1. is monotone non-decreasing
T(n) satisfies the following recurrence:

T(n) ≤ n + 1 / n [ 2T(n / 2) + … + 2T(n – 3) + 2T(n – 2) + 2T(n – 1) ]

≤ n + 1 / n [ 8(n / 2) + … + 8(n – 3) + 8(n – 2) + 8(n – 1) ]
inductive hypothesis
≤ n + 1 / n (3n2)
= 4 n. ▪ tiny cheat: sum should start at T(⎣n/2⎦)
45
Selection 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!

⇒ T(n) = Θ(n)

we’ll need to show this

46
Choosing 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

22 44 52 11 53 12 13 43 20 4 27

28 23 6 26 40 19 1 46 31 49 8

14 9 5 3 54 30 48 47 32 51 21

45 39 50 15 25 16 41 17 22 7

n = 54 47
Choosing 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 37 2 55 18 24 34 35 36

22 44 52 11 53 12 13 43 20 4 27

28 23 6 26 40 19 1 46 31 49 8

14 9 5 3 54 30 48 47 32 51 21

45 39 50 15 25 16 41 17 22 7

n = 54 48
 Choosing 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 median-of-medians as pivot element.
medians

median of
medians
29 10 38 37 2 55 18 24 34 35 36

22 44 52 11 53 12 13 43 20 4 27

28 23 6 26 40 19 1 46 31 49 8

14 9 5 3 54 30 48 47 32 51 21

45 39 50 15 25 16 41 17 22 7

n = 54 49
Median-of-medians selection algorithm

MOM-SELECT(A, k)
_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

n ← | A |.
IF (n < 50)
RETURN kth smallest of element of A via mergesort.


Group A into ⎣n / 5⎦ groups of 5 elements each (ignore leftovers).
B ← median of each group of 5.
p ← MOM-SELECT(B, ⎣n / 10⎦) median of medians



(L, M, R) ← PARTITION-3-WAY(A, p).
IF (k ≤ | L |) RETURN MOM-SELECT(L, k).
ELSE IF (k > | L | + | M |) RETURN MOM-SELECT(R, k – | L | – | M |)
ELSE RETURN p.
_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

50
 Analysis of median-of-medians selection algorithm

At least half of 5-element medians ≤ p.

medians

median of
medians p 29 10 38 37 2 55 18 24 34 35 36

22 44 52 11 53 12 13 43 20 4 27

28 23 6 26 40 19 1 46 31 49 8

14 9 5 3 54 30 48 47 32 51 21

45 39 50 15 25 16 41 17 22 7

n = 54 51
 Analysis of median-of-medians selection algorithm

At least half of 5-element medians ≤ p.

At least ⎣⎣n / 5⎦ / 2⎦ = ⎣n / 10⎦ medians ≤ p.

medians ≤ p

median of
medians p 29 10 38 37 2 55 18 24 34 35 36

22 44 52 11 53 12 13 43 20 4 27

28 23 6 26 40 19 1 46 31 49 8

14 9 5 3 54 30 48 47 32 51 21

45 39 50 15 25 16 41 17 22 7

n = 54 52
 Analysis of median-of-medians selection algorithm

At least half of 5-element medians ≤ p.

At least ⎣⎣n / 5⎦ / 2⎦ = ⎣n / 10⎦ medians ≤ p.
At least 3 ⎣n / 10⎦ elements ≤ p.

medians ≤ p

median of
medians p 29 10 38 37 2 55 18 24 34 35 36

22 44 52 11 53 12 13 43 20 4 27

28 23 6 26 40 19 1 46 31 49 8

14 9 5 3 54 30 48 47 32 51 21

45 39 50 15 25 16 41 17 22 7

n = 54 53
 Analysis of median-of-medians selection algorithm

At least half of 5-element medians ≥ p.

medians

median of
medians p 29 10 38 37 2 55 18 24 34 35 36

22 44 52 11 53 12 13 43 20 4 27

28 23 6 26 40 19 1 46 31 49 8

14 9 5 3 54 30 48 47 32 51 21

45 39 50 15 25 16 41 17 22 7

n = 54 54
 Analysis of median-of-medians selection algorithm

At least half of 5-element medians ≥ p.

At least ⎣⎣n / 5⎦ / 2⎦ = ⎣n / 10⎦ medians ≥ p.

medians ≥ p

median of
medians p 29 10 38 37 2 55 18 24 34 35 36

22 44 52 11 53 12 13 43 20 4 27

28 23 6 26 40 19 1 46 31 49 8

14 9 5 3 54 30 48 47 32 51 21

45 39 50 15 25 16 41 17 22 7

n = 54 55
 Analysis of median-of-medians selection algorithm

At least half of 5-element medians ≥ p.

At least ⎣⎣n / 5⎦ / 2⎦ = ⎣n / 10⎦ medians ≥ p.
At least 3 ⎣n / 10⎦ elements ≥ p.

medians ≥ p

median of
medians p 29 10 38 37 2 55 18 24 34 35 36

22 44 52 11 53 12 13 43 20 4 27

28 23 6 26 40 19 1 46 31 49 8

14 9 5 3 54 30 48 47 32 51 21

45 39 50 15 25 16 41 17 22 7

n = 54 56
Median-of-medians selection algorithm recurrence

Median-of-medians 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 any array of n elements.

 11
C(n) C ( n/5 ) + C (n 3 n/10 ) + 5 n


median of recursive computing median of 5


 medians select (≤ 6 compares per group)
partitioning


 (≤ n compares)


Intuition.
C(n) is going to be at least linear in n ⇒ C(n) is super-additive.
Ignoring floors, this implies that C(n) ≤ C(n / 5 + n − 3n / 10) + 11/5 n
= C(9n / 10) + 11/5 n
⇒ C(n) ≤ 22n. 57
Median-of-medians selection algorithm recurrence

Median-of-medians 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 any array of n elements.


 11
C(n) C ( n/5 ) + C (n 3 n/10 ) + 5 n


median of recursive computing median of 5


 medians select (≤ 6 compares per group)
partitioning


 (≤ n compares)


Now, let’s solve given recurrence.
Assume n is both a power of 5 and a power of 10 ?
Prove that C(n) is monotone non-decreasing.

58
Divide-and-conquer: quiz 4

Consider the following recurrence




0 n 1


C(n) =

 C( n/5 ) + C(n 3 n/10 ) + 11
<latexit sha1_base64="Y96HaCEvN4aOrD6hbv5tphcOY0Y=">AAAC0nicbVHLbtNAFB2bVwmPpmXJ5ooIlAoRbCCiKKJUyoZlkTCtlLGi8fg6HXU8tmbGKJGVBWLLj/BJ/A1j1xJNwl0dnXOf5yalFMYGwR/Pv3X7zt17e/d7Dx4+erzfPzj8ZopKc4x4IQt9kTCDUiiMrLASL0qNLE8knidX00Y//47aiEJ9tasS45wtlMgEZ9ZR8/7v6VAdAZ18pJMeTXAhVM1dO7Pu0UkAL4BaXFqoQWSwBgVUIoRA6SzEPHYp0yGVmSwKDer1GKhu8RG8BNcWXsFb+CeHwU2dZprxOgzX9bjpuzPopB3To6jSbqF5fxCMgjZgF4QdGJAuzuYH3iFNC17lqCyXzJhZGJQ2rpm2gkt0F1YGS8av2AJnDiqWo4nr1tM1PHdMCplbPSuUhZa9WVGz3JhVnrjMnNlLs6015P+0WWWz47gWqqwsKn49KKsk2AKaB0EqNHIrVw4wroXbFfglc25Z98aNKW3vEvnGJfWyUoIXKW6x0i6tZo2L4bZnuyB6M/owCr+8G5wed3bukafkGRmSkLwnp+QzOSMR4d6+N/ZOvE9+5Nf+D//ndarvdTVPyEb4v/4Ck0DZRw==</latexit>
5 n n>1


Is C(n) monotone non-decreasing?

A. Yes, obviously.

B. Yes, but proof is tedious.

C. Yes, but proof is hard.

D. No.

C(19) = 165
C(20) = 134.2

59
 Median-of-medians selection algorithm recurrence

Analysis of selection algorithm recurrence.

T(n) = max # compares on any array of ≤ n elements.
T(n) is monotone non-decreasing, but C(n) is not!


6n n < 50

 T (n)

 <latexit sha1_base64="uCnTptmZk5k2uvfF1msqYvcMsiY=">AAAC9HicbVFNj9MwEHXC11K+usuRy4gK1Aq2xEBhUTmsxIXjIrV0pboqjjvpWus4ke1Aq6g/hRPiyh/hF/BvcNJKbFvm9PTeeObNc5wraV0U/QnCa9dv3Lx1cLtx5+69+w+ah0efbVYYgUORqcycx9yikhqHTjqF57lBnsYKR/Hlh0offUVjZaYHbpnjJOVzLRMpuPPUtPl70NYdYH2mkPUbLMa51KXwA+2qwfpvNDwF5nDhoASZwAo0vIdeBIyNKaYT3wIs5QtgpZ8BftYx7Tz3cNBmKlFZZkC/6AEzNe7As6oFjuEV/JNpdFVnieGipHRV9vyyyhmw1b4JNse1jQZDPdsYnjZbUTeqC/YB3YAW2dTZ9DA4YrNMFClqJxS3dkyj3E1KbpwUCn0ChcWci0s+x7GHmqdoJ2Wd+gqeeGYGiT8iybSDmr36ouSptcs09p0pdxd2V6vI/2njwiUnk1LqvHCoxXpRUihwGVRfCDNpUDi19IALI71XEBfc5+b8R29tqWfnKLYuKReFliKb4Q6r3MIZXqVIdzPbB8OX3Xdd+ul16/RkE+cBeUQekzah5C05JR/JGRkSEdBgFHwJePgt/B7+CH+uW8Ng8+Yh2arw118pF+RQ</latexit>
max{ T (n 1), T ( n/5 ) + T (n 3 n/10 ) + 11
5 n) } n 50


Claim. T(n) ≤ 44 n.
Pf. [ by strong induction ]
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 either T(n) ≤ T(n – 1) ≤ 44 n or

T(n) ≤ T(⎣n / 5⎦) + T(n – 3 ⎣n / 10⎦) + 11/5 n

inductive
hypothesis ≤ 44 (⎣n / 5⎦) + 44 (n – 3 ⎣n / 10⎦) + 11/5 n
≤ 44 (n / 5) + 44 n – 44 (n / 4) + 11/5 n for n ≥ 50, 3 ⎣n / 10⎦ ≥ n / 4

= 44 n. ▪ 60
Divide-and-conquer: quiz 5

Suppose that we divide n elements into ⎣n / r⎦ groups of r elements each,

and use the median-of-medians of these ⎣n / r⎦ groups as the pivot.
For which r is the worst-case running time of select O(n) ?

A. r = 3 T(n) = T(n / 3) + T(n − 2n / 6) + Θ(n) ⇒ T(n) = Θ(n log n)

B. r = 7 T(n) = T(n / 7) + T(n − 4n / 14) + Θ(n) ⇒ T(n) = Θ(n)

C. Both A and B.

D. Neither A nor B.

61
Linear-time selection retrospective

Proposition. [Blum–Floyd–Pratt–Rivest–Tarjan 1973] There exists a

compare-based selection algorithm whose worst-case running time is O(n).
JOURNAL OF COMPUTER AND SYSTEM SCIENCES 7, 4 4 8 - 4 6 1 (1973)




Time Bounds for Selection*

 MANUEL BLUM, ROBERT W . FLOYD, VAUGHAN PRATT,



RONALD L . RIVEST, AND ROBERT E. TARJAN

Department of Computer Science, Stanford University, Stanford, California 94305


 Received November 14, 1972


 The number of comparisons required to select the i-th smallest of n numbers is shown



to be at most a linear function of n by analysis of a new selection algorithm--PICK.
Specifically, no more than 5.4305 n comparisons are ever required. This bound is
improved for extreme values of i, and a new lower bound on the requisite number


 of comparisons is also proved.


 1. INTRODUCTION

Theory. In this paper we present a new selection algorithm, PICK, and derive by an analysis
of its efficiency the (surprising) result that the cost of selection is at most a linear

Optimized version of BFPRT: ≤ 5.4305 n compares.

function of the number of input items. In addition, we prove a new lower bound
for the cost of selection.
The selection problem is perhaps best exemplified by the computation of medians.
Upper bound: [Dor–Zwick 1995] ≤ 2.95 n compares.
In general, we may wish to select the i-th smallest of a set of n distinct numbers,
or the element ranking closest to a given percentile level.
Lower bound: [Dor–Zwick 1999] ≥ (2 + 2
Interest in this problem may be traced to the realm−80
) n compares.
of sports and the design of
(traditionally, tennis) tournaments to select the first- and second-best players. In



1883, Lewis Carroll published an article [1] denouncing the unfair method by which
the second-best player is usually determined in a "knockout tournament" -- the loser
of the final match is often not the second-best! (Any of the players who lost only
Practice. Constants too large to be useful.
to the best player may be second-best.) Around 1930, Hugo Steinhaus brought the
62
problem into the realm of algorithmic complexity by asking for the minimum number
of matches required to (correctly) select both the first- and second-best players
 5. D IVIDE AND C ONQUER

‣ mergesort
‣ counting inversions
‣ randomized quicksort
‣ median and selection
‣ closest pair of points

SECTION 5.4
Closest 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

64
Closest pair of points

Closest pair problem. Given n points in the plane, find a pair of points

with the smallest Euclidean distance between them.


Brute force. Check all pairs with Θ(n2) distance calculations.


1D version. Easy O(n log n) algorithm if points are on a line.


Non-degeneracy assumption. No two points have the same x-coordinate.

65
Closest pair of points: first attempt

Sorting solution.
Sort by x-coordinate and consider nearby points.
Sort by y-coordinate and consider nearby points.

66
Closest pair of points: first attempt

Sorting solution.
Sort by x-coordinate and consider nearby points.
Sort by y-coordinate and consider nearby points.

67
Closest pair of points: second attempt

Divide. Subdivide region into 4 quadrants.

68
Closest pair of points: second attempt

Divide. Subdivide region into 4 quadrants.

Obstacle. Impossible to ensure n / 4 points in each piece.

69
Closest pair of points: divide-and-conquer 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. seems like Θ(n2)

21
8

12

70
How to find closest pair with one point in each side?

Find closest pair with one point in each side, assuming that distance < δ.
Observation: suffices to consider only those points within δ of line L.

21

12 δ = min(12, 21)

71
δ
How to find closest pair with one point in each side?

Find closest pair with one point in each side, assuming that distance < δ.
Observation: suffices to consider only those points within δ of line L.
Sort points in 2 δ-strip by their y-coordinate.
Check distances of only those points within 7 positions in sorted list!
why?

5
4
21

12 δ = min(12, 21)
3

72
δ
How to find closest pair with one point in each side?

Def. Let si be the point in the 2 δ-strip, with the ith smallest y-coordinate.


Claim. If ⎜j – i⎟ > 7, then the distance between

si and sj is at least δ. L



Pf.
Consider the 2δ-by-δ rectangle R in strip
 sj

whose min y-coordinate is y-coordinate of si.

Distance between si and any point sj

R ½δ
above R is ≥ δ.
diameter is δ
Subdivide R into 8 squares. / 2 <
<latexit sha1_base64="Pfe5G3M0P8ASzqZ7Xob9I+XpZXk=">AAACT3icdVDBTuMwEHXKsgsFllKOXKytWO0pJKWlRewBicseuxIFpKaqHGcKFo6TtSeoVdQ/4Gu4Ll/BjT/hhNbJFokieJKtp/dmPJ4XplIY9LxHp7L0afnzl5XV6tr6xtfN2lb9zCSZ5tDniUz0RcgMSKGgjwIlXKQaWBxKOA+vTwr//Aa0EYk6xWkKw5hdKjEWnKGVRrXvQQQSGQ2O6F5xBeaPxrw5K/jPUij9Ua3hue2D/U63RT3XP2zvN5sFabW7nRb1Xa9Eg8zRG2059SBKeBaDQi6ZMQPfS3GYM42CS5hVg8xAyvg1u4SBpYrFYIZ5udCM7lolouNE26OQlurrjpzFxkzj0FbGDK/MW68Q3/MGGY67w1yoNENQ/P+gcSYpJrRIh0ZCA0c5tYRxLexfKb9imnG0GS5MKd9OgS9skk8yJXgSwRtV4gQ1m9kUX6KiH5N+0z10/d+txnF3HucK2SHfyA/ikw45Jr9Ij/QJJ7fkjvwl986D8+Q8V+alFWdOtskCKqv/AOSCstc=</latexit>

½δ
At most 1 point per square.
si
At most 7 other points can be in R. ▪

constant can be improved with more


refined geometric packing argument

2δ
73
Closest pair of points: divide-and-conquer algorithm

CLOSEST-PAIR(p1, p2, …, pn)

_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
__________________________________________

Compute vertical line L such that half the points
 O(n)

are on each side of the line.
δ1 ← CLOSEST-PAIR(points in left half). T(n / 2)

δ2 ← CLOSEST-PAIR(points in right half). T(n / 2)

δ ← min { δ1 , δ2 }.
Delete all points further than δ from line L. O(n)

Sort remaining points by y-coordinate. O(n log n)

Scan points in y-order and compare distance between


each point and next 7 neighbors. If any of these
 O(n)
distances is less than δ, update δ.
RETURN δ.
_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
__________________________________________

74
Divide-and-conquer: quiz 6

What is the solution to the following recurrence?







 (1) n=1
T (n) =

 T ( n/2 ) + T ( n/2 ) + (n log n) n>1
<latexit sha1_base64="dpqSXns9eMyDq5iq+L5bY9kUO1I=">AAAC2nicbVFNixNBEO0Zv9b4lV0PHrwUZpUEIc4swq6ElQVBPa6QuAvpIfR0apJme7qH7h5JGHLyJF79I/4c/4092VkwiXV6vFdVrz7SQgrrouhPEN66fefuvb37rQcPHz1+0t4/+Gp1aTiOuJbaXKbMohQKR044iZeFQZanEi/Sqw+1fvENjRVaDd2ywCRnMyUywZnz1KT9e9hVPTiFFk1xJlTFfS+7atEBHc7RsW7cg1dAHS5cBSKDQ+Vz40NYAaXjqH+MeeJzh10qM6m1AfXmCKhZ4x7QwWs6gFrkKGSj1fBGajwUUKlnoHas3t9YtSiqaTPbpN2J+tE6YBfEDeiQJs4n+8EBnWpe5qgcl8zacRwVLqmYcYJL9MuWFgvGr9gMxx4qlqNNqvVtV/DSM1PI/G6ZVg7W7L8VFcutXeapz8yZm9ttrSb/p41Ll50klVBF6VDxa6OslOA01I+CqTDInVx6wLgRflbgc2YYd/6dGy7r3gXyjU2qRakE11PcYqVbOMPqK8bbN9sFo6P+u3785W3n7KQ55x55Tl6QLonJMTkjn8k5GREePAtOg4/BpzAJv4c/wp/XqWHQ1DwlGxH++gt4httm</latexit>

A. T(n) = Θ(n).

B. T(n) = Θ(n log n).

C. T(n) = Θ(n log2 n).

D. T(n) = Θ(n2).

75
Refined version of closest-pair algorithm

Q. How to improve to O(n log n) ?

A. Don’t sort points in strip from scratch each time.
Each recursive call returns two lists: all points sorted by x-coordinate,

and all points sorted by y-coordinate.
Sort by merging two pre-sorted lists.




Theorem. [Shamos 1975] The divide-and-conquer algorithm for finding a
closest pair of points in the plane can be implemented in O(n log n) time.


(1) n=1
Pf. T (n) =
<latexit sha1_base64="3pQz3or04sCHqNIWE5a09TyF+wA=">AAAC03icbVFNb9NAEF27fJTwlZYjlxEpKBFSaleIFkVAJC4ci5S0lbJWtN6Mk1XXa2t3XSUyuSCu/BH+Ef+GtetKJGFOT+/NzJuPOJfC2CD44/l79+4/eLj/qPX4ydNnz9sHhxcmKzTHMc9kpq9iZlAKhWMrrMSrXCNLY4mX8fWXSr+8QW1EpkZ2lWOUsrkSieDMOmra/j3qqh58hBaNcS5UyV0vs27RAR0t0LJu2IM3QC0ubQkigSPlcsMjWAOlk6B/imnkckddKhOZZRrU8QlQXeMe0MFbOoBK5Chko1XwTmo81I7HpzuPFkU1a4aatjtBP6gDdkHYgA5p4nx64B3SWcaLFJXlkhkzCYPcRiXTVnCJbsvCYM74NZvjxEHFUjRRWR91Da8dM4PELZVkykLN/ltRstSYVRq7zJTZhdnWKvJ/2qSwyVlUCpUXFhW/NUoKCTaD6kMwExq5lSsHGNfCzQp8wTTj1v1xw6XunSPf2KRcFkrwbIZbrLRLq1l1xXD7ZrtgfNL/0A+/vesMz5pz7pOX5BXpkpCckiH5Ss7JmHCv7b33PntD/8L/7v/wf96m+l5T84JshP/rL+PW2NQ=</latexit>
T ( n/2 ) + T ( n/2 ) + (n) n>1

76
Divide-and-conquer: quiz 7

What is the complexity of the 2D closest pair problem?


A. Θ(n).

B. Θ(n log* n).

C. Θ(n log log n).

D. Θ(n log n).

E. Not even Tarjan knows.

77
Computational complexity of closest-pair problem

Theorem. [Ben-Or 1983, Yao 1989] In quadratic decision tree model, any
algorithm for closest pair (even in 1D) requires Ω(n log n) quadratic tests.



(x1 - x2)2 + (y1 - y2)2











Theorem. [Rabin 1976] There exists an algorithm to find the closest pair of
points in the plane whose expected running time is O(n).
Volume 8, number 1 IhFCRMATION PROCESSING LE,TTERS January 1979

A NOTE ON RABIN’S NEAREST-NEIGHBOR ALGORITHM * not subject to Ω(n log n) lower bound
because it uses the floor function
Steve FORTUNE and John HOPCROFT
Department of Computer Science, Cornell University,Ithaca, NY, U.S.A.

Received 20 July 1978, revised version received 21 August 1978

Probabiktic algorithms, nearest neighbor, hashing

78
Digression: computational geometry

Ingenious divide-and-conquer algorithms for core geometric problems.







problem brute clever



 closest pair O(n2) O(n log n)


 farthest pair O(n2) O(n log n)



convex hull O(n2) O(n log n)



 Delaunay/Voronoi O(n4) O(n log n)


Euclidean MST O(n2) O(n log n)


running time to solve a 2D problem with n points






Note. 3D and higher dimensions test limits of our ingenuity.

79
Convex hull

The convex hull of a set of n points is the smallest perimeter fence


enclosing the points.






















Equivalent definitions.
Smallest area convex polygon enclosing the points.
Intersection of all convex set containing all the points.

80
Farthest pair

Given n points in the plane, find a pair of points with the largest Euclidean
distance between them.

Fact. Points in farthest pair are extreme points on convex hull.

81
Delaunay triangulation

The Delaunay triangulation is a triangulation of n points in the plane


such that no point is inside the circumcircle of any triangle.





 no point in the set is

inside the circumcircle









 point inside circumcircle
of 3 points




Delaunay triangulation of 19 points


Some useful properties.
No edges cross.
Among all triangulations, it maximizes the minimum angle.
Contains an edge between each point and its nearest neighbor. 82
Euclidean MST

Given n points in the plane, find MST connecting them.


[distances between point pairs are Euclidean distances]






















Fact. Euclidean MST is subgraph of Delaunay triangulation.
Implication. Can compute Euclidean MST in O(n log n) time.
Compute Delaunay triangulation.
it’s planar
Compute MST of Delaunay triangulation. (≤ 3n edges) 83
Computational geometry applications

Applications.
Robotics.
VLSI design.
Data mining.
Medical imaging.
Computer vision.
Scientific computing.
airflow around an aircraft wing
Finite-element meshing.
Astronomical simulation.
Models of physical world.
Geographic information systems.
Computer graphics (movies, games, virtual reality).

http://www.ics.uci.edu/~eppstein/geom.html

84