COMP90038
Algorithms and Complexity
Lecture 11: Sorting with Divide-and-Conquer
(with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Divide and Conquer
We earlier studied recursion as a powerful problem
•
solving technique.
The divide-and-conquer strategy tries to make the most
1. Divide the given problem instance into smaller
instances.
2. Solve the smaller instances recursively.
3. Combine the smaller solutions to solve the original instance.
•
of this idea:
This works best when the smaller instances can be made
•
to be of equal (or near-equal) size.
Split-Solve-and-Join
Approach
3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Divide and Conquer Algorithms
•
•
We will discuss:
The Master Theorem
Mergesort
Quicksort
Tree traversal Closest Pair revisited
• • • •
Divide-and-Conqer General Case
problem of size n
problem of size n/b
problem of size n/b
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
problem of size n/b
…
problem of size n/b
b sub-problems
Divide-and-Conqer General Case
problem of size n
problem of size n/b
problem of size n/b
6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
problem of size n/b
…
problem of size n/b
only a sub-problems need to be solved
Divide-and-Conqer General Case
problem of size n
problem of size n/b
problem of size n/b
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
problem of size n/b
…
problem of size n/b
only a sub-problems need to be solved
combine the a solutions
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Divide-and-Conquer Recurrences
What is the time required to solve a problem of size n by
•
divide-and-conquer?
For the general case, assume we split the problem into b
•
instances (each of size n/b), of which a need to be
• •
solved:
T(n) = aT(n/b) + f(n)
where f(n) expresses the time spent on dividing a problem
into b sub-problems and combining the a results. (A very common case is T(n) = 2T(n/2) + n.)
How to find closed forms for these recurrences?
The Master Theorem
(A proof is in Levitin’s Appendix B.)
For integer constants a ≥ 1 and b > 1, and function
f with f(n) ∈ Θ(nd), d ≥ 0, the recurrence
• •
T(n) = aT(n/b) + f(n)
9
•
(with T(1) = c) has solutions, and
Note that we also allow a to be greater than b. Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1 a = bd
So, by the Master Theorem, T(n) ∈ Θ(n log n) 11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 2(2T(n/4) + (n/2)) + n
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 4T(n/4) + 2(n/2) + n
14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 4(2T(n/8) + n/4) + 2(n/2) + n
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 8T(n/8) + 4(n/4) + 2(n/2) + n
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 8(2T(n/16) + n/8) + 4(n/4) + 2(n/2) + n
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) = 16T(n/16) + 8(n/8) + 4(n/4) + 2(n/2) + n
18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 1
T(n) = 2T(n/2) + n a = 2, b = 2, d = 1
T(n) ∈ Θ(n log n)
20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1 a = bd
So, by the Master Theorem, T(n) ∈ Θ(n log n) 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 4(4T(n/16) + (n/4)) + n
23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 16T(n/16) + 4(n/4) + n
24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 16T(n/16) + 4(n/4) + n
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 16(4T(n/64) + n/16) 4(n/4) + n
26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n
27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n
(log4 n times)
28 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
…
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n
(log4 n times)
29 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
…
Master Theorem: Example 2
T(n) = 4T(n/4) + n a = 4, b = 4, d = 1
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n T(n) ∈ Θ(n log n)
30 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 3
T(n) = T(n/2) + n a = 1, b = 2, d = 1
31 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 3
T(n) = T(n/2) + n a = 1, b = 2, d = 1 a < bd
So, by the Master Theorem, T(n) ∈ Θ(n)
32 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 3
T(n) = T(n/2) + n a = 1, b = 2, d = 1
33 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 3
T(n) = T(n/2) + n a = 1, b = 2, d = 1
T(n) = T(n/4) + n/2 + n
34 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 3
T(n) = T(n/2) + n a = 1, b = 2, d = 1
T(n) = T(n/8) + n/4 + n/2 + n
35 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 3
T(n) = T(n/2) + n a = 1, b = 2, d = 1
T(n) = T(n/8) + n/4 + n/2 + n
36 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 3
T(n) = T(n/2) + n a = 1, b = 2, d = 1 T(n) = T(n/8) + n/4 + n/2 + n
T(n) ∈ Θ(n)
37 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2
38 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2 a < bd
So, by the Master Theorem, T(n) ∈ Θ(n2)
39 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2
40 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2
T(n) = 2(2T(n/4) + (n/2)2) + n2
41 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2
T(n) = 4T(n/4) + 2(n/2)2 + n2
42 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2
T(n) = 4(2T(n/8) + (n/4)2) + 2(n/2)2 + n2
43 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2
T(n) = 8T(n/8) + 4(n/4)2 + 2(n/2)2 + n2
44 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2
T(n) = 8T(n/8) + 4(n/4)2 + 2(n/2)2 + n2
45 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2 T(n) = 8T(n/8) + 4(n/4)2 + 2(n/2)2 + n2
T(n) ∈ Θ(n2)
46 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort
Perhaps the most obvious application of divide-and-conquer:
•
To sort an array (or a list), cut it into two halves, sort each half,
•
and merge the two results.
47
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
48
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
49
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
50
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
51
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
52
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
53
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
54
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
55
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
56
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
57
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
58
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
59
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
60
Mergesort
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort
61 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
62 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
63
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
64
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
65
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
66
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
67
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
68
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
69
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
70
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
71
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
72
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
73
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
74
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
75
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
76
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
77
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
78
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
7
79
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
7
80
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
7
81
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
82 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
7
83
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
7
8
84
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
7
8
85
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
7
8
86
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Merging Arrays
1
4
5
7
2
3
8
9
B:
C:
0123 0123
ij
A:
01234567
k
p: 4 q: 4
1
2
3
4
5
7
8
9
87
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Analysis
How many comparisons will MERGE need to make
•
in the worst case, when given arrays of size ⌊n/2⌋
•
and ⌈n/2⌉ ?
If the largest and second-largest elements are in different arrays, then n − 1 comparisons. Hence the cost equation for Mergesort is
By the Master Theorem, C(n) ∈ Θ(n log n).
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
88
•
89
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Properties
For large n, the number of comparisons made tends Is mergesort stable? ?
no
If comparisons are fast, mergesort ranks between quicksort and heapsort (covered next week) for time, assuming random data.
•
to be around 75% of the worst-case scenario.
• • •
Is mergesort in-place?
Mergesort is the method of choice for linked lists
•
and for very large collections of data.
Mergesort: Stability
3
3
3
3
3
3
3
3
3333
3
3
3
3
3
3
3
3
90 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
91
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Mergesort: Properties
For large n, the number of comparisons made tends Is mergesort stable? yes
no
If comparisons are fast, mergesort ranks between quicksort and heapsort (covered next week) for time, assuming random data.
•
to be around 75% of the worst-case scenario.
• • •
Is mergesort in-place?
Mergesort is the method of choice for linked lists
•
and for very large collections of data.
Bottom-Up Mergesort
An alternative way of doing mergesort:
Generate runs of length 2, then of length 4, and so
•
•
on:
92
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort
It uses the partitioning idea from QuickSelect, picking a pivot element, and partitioning the array around that, so as to obtain this situation:
Quicksort takes a divide-and-conquer approach that is
•
different to mergesort’s.
•
93
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
The element A[s] will be in its final position (it is the (s + 1)th
•
smallest element).
All that then needs to be done is to sort the segment to the
•
left, recursively, as well as the segment to the right.
94
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort
Very short and elegant:
Initial call: Quicksort(A, 0, n − 1).
•
•
Quicksort: Example
9
23
8
41
22
3
37
A:
0123456
95 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
8
3
9
41
22
23
37
A:
0123456
96 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
8
3
9
41
22
23
37
A:
0123456
97 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
3
8
9
41
22
23
37
A:
0123456
98 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
3
8
9
41
22
23
37
A:
0123456
99 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
3
8
9
37
22
23
41
A:
0123456
100 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
3
8
9
37
22
23
41
A:
0123456
101 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
3
8
9
23
22
37
41
A:
0123456
102 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
3
8
9
23
22
37
41
A:
0123456
103 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
3
8
9
22
23
37
41
A:
0123456
104 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort: Example
3
8
9
22
23
37
41
A:
0123456
105 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
The standard way of doing partitioning in Quicksort
•
106
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
23
8
41
22
3
37
p: 9
ij
A:
0123456
107 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
23
8
41
22
3
37
p: 9
ij
A:
0123456
108 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
23
8
41
22
3
37
p: 9
ij
A:
0123456
109 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
3
8
41
22
23
37
p: 9
ij
A:
0123456
110 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
3
8
41
22
23
37
p: 9
ij
A:
0123456
111 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
3
8
41
22
23
37
p: 9
ij
A:
0123456
112 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
3
8
41
22
23
37
p: 9
ij
A:
0123456
113 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
3
8
41
22
23
37
p: 9
i j
A:
0123456
114 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
3
8
41
22
23
37
p: 9
ji
A:
0123456
115 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
3
41
8
22
23
37
p: 9
ji
A:
0123456
116 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
9
3
8
41
22
23
37
p: 9
ji
A:
0123456
117 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Hoare Partitioning
8
3
9
41
22
23
37
p: 9
ji
A:
0123456
118 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
119
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Analysis:
Best Case Analysis
The best case happens when the pivot is the median; that results in two sub-tasks of equal size.
The ‘n’ is for the n key comparisons performed by Partition.
By the Master Theorem, Cbest(n) ∈ Θ(n log n), just
as for mergesort, so quicksort’s best case is (asymptotically) no better than mergesort’s worst case.
•
•
Quicksort Worst Case
4
9
13
22
41
83
96
A:
0123456
120 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Analysis:
Worst Case Analysis
The worst case happens if the array is already
•
sorted.
•
In that case, we don’t really have divide-and- conquer, because each recursive call deals with a problem size that has only been decremented by 1:
That is, Cworst(n) = n + (n − 1) + · · · + 3 + 2 ∈ Θ(n2). Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
121
•
122
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Improvements: Median-of-Three
•
It would be better if the pivot was chosen randomly.
A cheap and useful approximation to this is to take
•
the median of three candidates, A[lo], A[hi], and
A[⌊(lo + hi)/2⌋].
Reorganise the three elements so that p1 is the
•
median, and p3 is the largest of the three.
•
Now run quicksort as before.
Quicksort Improvements: Median-of-Three
In fact, with median-of-three, we can have a much faster
•
version than before, simplifying tests in the innermost loops:
123
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Improvements: Early Cut-Off
A second useful improvement is to stop quicksort early
•
and switch to insertion sort. This is easily implemented:
124
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
125
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Properties
A major reason for its speed is the very tight inner loop in PARTITION.
•
•
In the best case, we get ⌈log2 n⌉ recursive levels. It can be shown that on random data, the expected number is 2 loge n ≈ 1.38 log2 n.
So quicksort’s average behaviour is very close to the best-case behaviour.
?
yes
• •
Is quicksort stable? Is it in-place?
With these (and other) improvements, quicksort is considered the
•
best available sorting method for arrays of random data.
Although mergesort has a better performance guarantee, quicksort
•
is faster on average.
Quicksort Stability
ij
2
2
1
126 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Stability
ij
2
2
1
127 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Stability
j i
2
2
1
128 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Stability
j i
1
2
2
129 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Stability
1
2
2
130 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Stability
This is where we finished
1
2
2
2
2
1
This is where we started
Not stable
131 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
132
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Quicksort Properties
A major reason for its speed is the very tight inner loop in PARTITION.
•
•
In the best case, we get ⌈log2 n⌉ recursive levels. It can be shown that on random data, the expected number is 2 loge n ≈ 1.38 log2 n.
So quicksort’s average behaviour is very close to the best-case behaviour.
no
yes
• •
Is quicksort stable? Is it in-place?
With these (and other) improvements, quicksort is considered the
•
best available sorting method for arrays of random data.
Although mergesort has a better performance guarantee, quicksort
•
is faster on average.
133
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Next up
Tree traversal methods, plus we apply the divide-
•
and-conquer technique to the closest-pair problem.