CS146 Data Structures and Algorithms
Chapter 7: Quicksort
L7.1
Quicksort
• Sorts in place
• Sorts O(n lg n) in the average case
• Sorts O(n2) in the worst case
§ But in practice, it’s quick
§ And the worst case doesn’t happen often (but more on this later…)
§ Empirical and analytical studies show that quicksort can be expected to be twice as fast as its competitors.
L7.2
7.1 Description of Quicksort
Quicksort an n-element array:
• Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray.
≤xx
≥x
• Conquer: Recursively sort the two subarrays.
• Combine: The subarrays are sorted in place – no
work is needed to combine them.
• How do the divide and combine steps of quicksort compare with those of merge sort?
L7.3
Design
• Key: Linear-time partitioning subroutine.
• Divide: Partition (separate) the array A[p..r] into two
(possibly empty) subarrays A[p..q–1] and A[q+1..r]. § Each element in A[p..q–1] £ A[q].
§ A[q] £ each element in A[q+1..r].
§ Index q is computed as part of the partitioning procedure.
A[p..r]
5
A[p..q – 1] A[q+1..r]
£5 35
Partition
5
L7.4
QUICKSORT(A, p, r) 1 if p < r
2 3 4
q = PARTITION(A, p, r) QUICKSORT(A, p, q-1) QUICKSORT(A, q+1, r)
Sorting Animation
Initial call: QUICKSORT(A, 1, n)
L7.5
Loop Invariant
1. All entries in A[p..i] are ≤ pivot.
2. All entries in A[i+1..j-1] are > pivot.
3. A[r] = pivot.
Loop Invariant
L7.6
Partition(A, p, r)
1 x = A[r]
2i =p–1
3 for j = p to r -1
4
5
6
7
8 return i+1
ifA[j]≤x i=i+1
exchange A[i] « A[j] exchange A[i+1] « A[r]
L7.7
The operation of Partition on a sample array
L7.8
1 x = A[r] 2i=p–1
3 for j = p to r -1
4
5
6
7
8 return i+1
ifA[j]≤x i=i+1
exchange A[i] « A[j] exchange A[i+1] « A[r]
Two cases for one iteration of procedure
Partition
Complexity:
Partition on A[p…r] is Q(n) where n = r –p +1
Why??? (Exercise 7.1-3)
L7.9
1 x = A[r] 2i=p–1
3 for j = p to r -1
4
5
6
7
8 return i+1
ifA[j]≤x
i=i+1
exchange A[i] « A[j
exchange A[i+1] « A[r]
]
Exercise 7.1-3
• Give a brief argument that the running time of PARTITION on a subarray of size n is Q(n).
Answer:
The for loop makes exactly r ̶ p iterations, each of which takes at most constant time. The part outside the for loop takes at most constant time. Since r ̶ p is the size of the subarray, PARTITION takes at most time proportional to the size of the subarray it is called on.
L7.10
Another partitioning example
pr 2 5 8 3 9 4 1 7 10 6
note:pivot(x)=6
1 x = A[r] 2i=p–1
3 for j = p to r -1
initially:
nextiteration: 25839417106
ij
ij
nextiteration: nextiteration: nextiteration:
2 5 8 3 9 4 1 7 10 6 ij
2 5 8 3 9 4 1 7 10 6 ij
2 5 3 8 9 4 1 7 10 6 ij
ifA[j]≤x
i=i+1
exchange A[i] « A[j]
4
5
6
7
8 return i+1
exchange A[i+1] « A[r]
L7.11
next iteration: next iteration: next iteration: next iteration: next iteration: next iteration:
Another example (Continued)
25389 4 1 7 106 ij
25389 4 1 7 106 ij
253498 1 7 106 ij
2534189 7 106 ij
25341897 106 ij
25341897106 ij
1 x = A[r] 2i=p–1
3 for j = p to r -1
4 5 6
ifA[j]≤x
i=i+1
exchange A[i] « A[j]
exchange A[i+1] « A[r]
7
8 return i+1
afterfinalswap: 25341697108 ij
L7.12
• •
Partitioning
Select the last element A[r] in the subarray A[p..r] as the pivot – the element around which to partition.
As the procedure executes, the array is partitioned
into four (possibly empty) regions.
1. A[p..i] — All entries in this region are £ pivot.
2. A[i+1..j – 1] — All entries in this region are > pivot.
3. A[r] = pivot.
4. A[j..r – 1] — Not known how they compare to pivot.
The above hold before each iteration of the for loop, and constitute a loop invariant. (4 is not part of the LI.)
•
L7.13
Correctness of Partition
• Use loop invariant. • Initialization:
§ Before first iteration
o A[p..i] and A[i+1..j – 1] are empty – Conds. 1 and 2 are satisfied
(trivially).
o r is the index of the pivot – Cond. 3 is satisfied.
• Maintenance:
§Case 1: A[j] > x o Increment j only. o LI is maintained.
1 x = A[r] 2i=p–1
3 for j = p to r -1
4 5 6
ifA[j]≤x
i=i+1
exchange A[i] « A[j]
exchange A[i+1] « A[r] L7.14
7
8 return i+1
Correctness of Partition
Case 1:
pijr
>x
x
£x p
£x
>x
ij
>x
r
x
L7.15
Correctness of Partition
• Case2:A[j]£x § Increment i
§ Swap A[i] and A[j]
o Condition 1 is maintained.
§ Increment j
o Condition 2 is maintained.
» A[r] is unaltered.
• Condition 3 is maintained.
pijr
£x
x
£x p
£x
>x
ij
>x
r
x
L7.16
Correctness of Partition
• Termination:
§ When the loop terminates, j = r, so all elements in A are partitioned into one of the three cases:
o A[p..i] £ pivot
o A[i+1..j – 1] > pivot o A[r] = pivot
• The last two lines swap A[i+1] and A[r].
§ Pivot moves from the end of the array to between
the two subarrays.
§ Thus, procedure partition correctly performs the divide step.
L7.17
Complexity of Partition
• PartitionTime(n) is given by the number of iterations in the for loop.
• Q(n): n=r–p+1.
1 x = A[r] 2i=p–1
3 for j = p to r -1
4 5 6
ifA[j]≤x
i=i+1
exchange A[i] « A[j]
exchange A[i+1] « A[r]
7
8 return i+1
L7.18
QUICKSORT(A, p, r) 1 if p < r
2 3 4
q = PARTITION(A, p, r) QUICKSORT(A, p, q-1) QUICKSORT(A, q+1, r)
Sorting Animation
Initial call: QUICKSORT(A, 1, n)
L7.19
Algorithm Performance
Running time of quicksort depends on whether the partitioning is balanced or not.
• Worst-Case Partitioning (Unbalanced Partitions): § Occurs when every call to partition results in the most
unbalanced partition.
§ Partition is most unbalanced when
o Subarray 1 is of size n – 1, and subarray 2 is of size 0 or vice versa.
o pivot 3 every element in A[p..r – 1] or pivot < every element in A[p..r – 1].
§ Every call to partition is most unbalanced when o Array A[1..n] is sorted or reverse sorted!
L7.20
Worst-case Partition Analysis
n
Recursion tree for worst-case partition
n n–1
n–2
n–3
2 1
Running time for worst-case partitions at each recursive level:
T(n) = T(n – 1) + T(0) + PartitionTime(n) = T(n – 1) + Q(n)
= åk=1 to nQ(k)
= Q(åk=1 to n k ) = Q(n(n+1)/2)
= Q(n2)
L7.21
Best-case Partitioning
• Size of each subarray £ n/2.
§ One of the subarray is of size ën/2û § The other is of size én/2ù -1.
• Recurrence for running time § T(n) £ 2T(n/2) + PartitionTime(n)
= 2T(n/2) + Q(n) • T(n)=Q(nlgn)
L7.22
Recursion Tree for Best-case Partition
cn
cn
cn/2
cn/2
cn
cn
lg n
cn/4
cn/4 cn/4
cn/4
ccc ccc
cn
: O(n lg n)
Total
L7.23
Variations
• Quicksort is not very efficient on small lists. • This is a problem because Quicksort will be
called on lots of small lists.
• Fix 1: Use Insertion Sort on small arrays.
• Fix 2: Leave small arrays unsorted. Fix with one final Insertion Sort at end.
§ Note: Insertion Sort is very fast on almost-sorted lists. L7.24
Unbalanced Partition Analysis
What happens if we get poorly-balanced partitions,
e.g., something like: T(n) £ T(9n/10) + T(n/10) + Q(n)?
Still get Q(n lg n)!! (As long as the split is of constant proportionality.)
Intuition: Can divide n by c > 1 only Q(lg n) times before getting 1. n
̄£n n/c
̄n/c2 Roughly logc n levels;
£n £n
̄
!
̄
1= n/clogcn
Cost per level is O(n).
(Remember: Different base logs are related by a constant.)
L7.25
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
L7.26
Intuition for the Average Case
• Partitioning is unlikely to happen in the same way at every level.
§ Split ratio is different for different levels. (Contrary to our assumption in the previous slide.)
• Partition produces a mix of “good” and “bad” splits, distributed randomly in the recursion tree.
• What is the running time likely to be in such a case?
L7.27
Analyzing Quicksort: Average Case
• Intuitively, a real-life run of quicksort will produce a mix of “bad” and “good” splits
§ Randomly distributed among the recursion tree
§ Pretend for intuition that they alternate between
best-case (n/2 : n/2) and worst-case (n-1 : 1)
§ What happens if we bad-split root node, then good-split the resulting size (n-1) node?
o We end up with three subarrays, size 1, (n-1)/2, (n-1)/2 o Combined cost of splits = n + n -1 = 2n -1 = O(n)
o No worse than if we had good-split the root node!
L7.28
n 0
(n – 1)/2 – 1
n
Produces subarrays of sizes 0, (n – 1)/2 – 1, and (n – 1)/2. Cost of partitioning :
Q(n) + Q(n-1) = Q(n). Good split at the first level:
Produces two subarrays of size (n – 1)/2.
Cost of partitioning :
Q(n).
Intuition for the Average Case
Bad split followed by a good split:
Q(n)
n–1
(n – 1)/2
Q(n)
(n – 1)/2
(n – 1)/2
Situation at the end of case 1 is not worse than that at the end of case 2. When splits alternate between good and bad, the cost of bad split can be absorbed into the cost of good split.
Thus, running time is O(n lg n), though with larger hidden constants.
L7.29
Randomized Quicksort
w Want to make running time independent of input ordering.
w How can we do that?
» Make the algorithm randomized.
» Make every possible input equally likely.
• Can randomly shuffle to permute the entire array.
• For quicksort, it is sufficient if we can ensure that every element is equally likely to be the pivot.
• So, we choose an element in A[p..r] and exchange it with A[r].
• Because the pivot is randomly chosen, we expect the partitioning to be well balanced on average.
L7.30
Randomized Version
Want to make running time independent of input ordering.
Randomized-Quicksort(A, p, r) if p < r
q = Randomized-Partition(A, p, r); Randomized-Quicksort(A, p, q – 1); Randomized-Quicksort(A, q + 1, r)
Randomized-Partition(A, p, r) i = Random(p, r);
exchange A[r] = A[i]; Partition(A, p, r)
L7.31
7.4 Analysis of quicksort
7.4.1 Worst-case analysis
T(n)= max (T(q)+T(n-q-1))+Q(n) 0£q£n-1
guess T(n)£cn2
T(n)£ max(cq2 +c(n-q-1)2)+Q(n)
0£q£n-1
=c max(q2 +(n-q-1)2)+Q(n)
0£q£n-1
£cn2 -2c(n-1)+Q(n)
£ cn2
pick the constant c large enough so that the 2c(n-1) term dominates
the Q(n) term. Þ T(n) = Q(n2 )
L7.32
7.4.2 Expected running time
• Running time and comparisons • Lemma 7.1
§ Let X be the number of comparisons performed in line 4 of partition over the entire execution of Quicksort on an n-element array. Then the running rime of Quicksort is O(n+X)
L7.33
we define
Xij = I {zi is compared to zj},
n-1 n
X = å åXij.
i=1 j=i+1
=n-1 n E[X ] åå ij
én-1n ù
E[X]=Eêå åXijú
êi=1 j=i+1 ú ëû
i=1 j=i+1
n-1 n {z is compared to z }
= å åPr i j i=1 j=i+1
L7.34
Pr{zi is compared to zj} = Pr{zi or zj is first pivot chosen from Zij} = Pr{zi is first pivot chosen from Zij}
+ Pr{zj is first pivot chosen from Zij}
=1+1 j-i+1 j-i+1
=
2
j - i +1
n-1n 2
\E[X]=åå j-i+1. i=1 j=i+1
L7.35
n-1n 2 E[X]=åå j-i+1
i=1 j=i+1 n-1n-i 2
= ååk +1 i=1k=1
n-1 n 2 < ååk
i=1k=1
n-1
= åO(lgn)
i=1 =O(nlgn)
by pp. 1147 A.7
L7.36