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] < xi = i +1swap A[i] and A[j] swap A[i+1] with A[end]4QuicksortSort: {4, 5, 3, 8, 1, 6, 2} 5QuicksortSort: {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 6Quicksort}For quicksort, you can pick any pivot you wantThe algorithm is just easier to write if you pick the last element (or first) 7QuicksortSort: {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} 8QuicksortCorrectness: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 itit stays put and claims a “larger” spot Termination: Loop on all elements… 9QuicksortRuntime: Worst case? Average?10QuicksortRuntime:Worst case?Always pick lowest/highest element, so O(n2)Average? 11QuicksortRuntime:Worst case?Always pick lowest/highest element, so O(n2)Average?Sort about half, so same as merge sort on average 12QuicksortCan 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) 13Quicksort= 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) 14QuicksortWhich is better for multi core, quicksort or merge sort? If the average run times are the same, why might you choose quicksort?15QuicksortWhich is better for multi core, quicksort or merge sort? Neither, quicksort front ends the processing, merge back endsIf the average run times are the same, why might you choose quicksort? 16QuicksortWhich is better for multi core, quicksort or merge sort? Neither, quicksort front ends the processing, merge back endsIf the average run times are the same, why might you choose quicksort? Uses less space. 17Quicksort
Reviews
There are no reviews yet.