1
More sorting
1. Pick a pivot (any element!)
2. Sort the list into 3 parts:
– Elements smaller than pivot – Pivot by itself
– Elements larger than pivot
3. Recursively sort smaller & larger
2
Quicksort
Pivot
Larger
Smaller
3
Quicksort
Partition(A, start, end) x = A[end]
i = start – 1
for j = start to end -1
if A[j] < x
i = i +1
swap A[i] and A[j]
swap A[i+1] with A[end]
4
Quicksort
Sort: {4, 5, 3, 8, 1, 6, 2}
5
Quicksort
Sort: {4, 5, 3, 8, 1, 6, 2} – Pivot = 2 {4, 5, 3, 8, 1, 6, 2} – sort 4
{4, 5, 3, 8, 1, 6, 2} – sort 5
{4, 5, 3, 8, 1, 6, 2} – sort 3
{4, 5, 3, 8, 1, 6, 2} – sort 8
{4, 5, 3, 8, 1, 6, 2} – sort 1, swap 4 {1, 5, 3, 8, 4, 6, 2} – sort 6
{1, 5, 3, 8, 4, 6, 2},{1, 2, 5, 3, 8, 4, 6
6
Quicksort
}
For quicksort, you can pick any pivot you want
The algorithm is just easier to write if you pick the last element (or first)
7
Quicksort
Sort: {4, 5, 3, 8, 1, 6, 2} - Pivot = 3 {4, 5, 2, 8, 1, 6, 3} – swap 2 and 3 {4, 5, 2, 8, 1, 6, 3}
{4, 5, 2, 8, 1, 6, 3}
{2, 5, 4, 8, 1, 6, 3} – swap 2 & 4
{2, 5, 4, 8, 1, 6, 3} (first red ^) {2, 1, 4, 8, 5, 6, 3} – swap 1 and 5 {2, 1, 4, 8, 5, 6, 3}{2, 1, 3, 8, 5, 6, 4}
8
Quicksort
Correctness:
Show: start to i (inclusive) is <= pivot,
and i to j (exclusive) is > pivot Base: Initially no elements are in the “smaller” or “larger” category
Step (loop): If A[j] < pivot it will be added to “smaller” and “smaller” will claim next spot, otherwise it
it stays put and claims a “larger” spot Termination: Loop on all elements...
9
Quicksort
Runtime: Worst case?
Average?
10
Quicksort
Runtime:
Worst case?
Always pick lowest/highest element, so O(n2)
Average?
11
Quicksort
Runtime:
Worst case?
Always pick lowest/highest element, so O(n2)
Average?
Sort about half, so same as merge sort on average
12
Quicksort
Can bound number of checks against pivot:
Let Xi,j = event A[i] checked to A[j]
sumi,j Xi,j = total number of checks E[sumi,j Xi,j]= sumi,j E[Xi,j]
= sumi,j Pr(A[i] check A[j])
= sumi,j Pr(A[i] or A[j] a pivot)
13
Quicksort
= sumi,j Pr(A[i] or A[j] a pivot)
= sumi,j (2 / j-i+1) // j-i+1 possibilties
(above is the Harmonic series) < sumi O(lg n)
= O(n lg n)
14
Quicksort
Which is better for multi core, quicksort or merge sort?
If the average run times are the same, why might you choose quicksort?
15
Quicksort
Which is better for multi core, quicksort or merge sort? Neither, quicksort front ends the processing, merge back ends
If the average run times are the same, why might you choose quicksort?
16
Quicksort
Which is better for multi core, quicksort or merge sort? Neither, quicksort front ends the processing, merge back ends
If the average run times are the same, why might you choose quicksort? Uses less space.
17
Quicksort