[SOLVED] CS algorithm 1

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