# 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] < 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