Notes from CS2040S Week 4 Lecture 1 on Quick Sort
if n = 1 return
else:
p = partition(A[1...n], n)
x = quicksort(A[1...p-1], p-1)
y = quicksort(A[p+1, n], n-p)For [6, 6, 6, 6, 6, 6], if the pivot is index 0, the runtime is O(n^2).
Ideally, we want to have an array with duplicates in the following 3-way partition form:
<x | x x x | >x
Using 3-way partition, Quick Sort is stable with duplicates if partition is stable. Though, in-place partition is not stable.
- First element
- Last element
- Middle element
- Median element
For worst-case analysis, all these options are equally bad.
Sorting the array takes n executions of partition. Each call to partition sorts one element.
total = low + high + partition
T(n) = T(n-1) + T(1) + n
= O(n^2)
total = low + high + partition
T(n) = T(n/2) + T(n/2) + kn
< 2T(n/2) + kn
= O(nlogn)
Assume the sorted side grows at 9n/10 rate
T(n) = T(9n/10) + T(9n/10) + kn
< O(nlogn)
The running time is a random variable. It can also fool the adversary who provides bad inputs. The algorithm makes decision based on random coin flips.
def paranoidQS(A, n): // T(n)
if (n == 1) return
else:
repeat
pIdx = random(1, n)
p = partition(A, n, pIdx) // O(n)
until p > n/10 and p < 9n/10
x = paranoidQS(A[1...p-1], p-1) // T(k)
y = paranoidQS(A[p+1...n], p-1) // T(n-k)This creates the following recurrence:
T(n) = T(k) + T(n-k) + c*T(n)
where c is the number of repetitions until a good pivot is chosen.
The expected runtime is O(nlogn) for random pivot selection.
Find kth smallest element in an unsorted element. Possible solutions:
- Option 1
- Sort array
- Count to element k
- Runtime:
O(nlogn)
- Option 2
- Only do minimum amount of sorting
- Partition the array and continue searching in the correct half
- The other half doesn't matter at all
Find 5th smallest element
9 22 13 17 5 3 100 6 19 8
Partition around random pivot: 17
9 8 13 5 3 6 17 100 19 22
Partition around random pivot: 8
6 3 5 8 13 9
Find minimum element in right half
Partition around random pivot: 13
9 13
-> return 9
select(A, n, k):
if (n == 1) return A[1]
else:
choose random pivot pIdx
p = partition(A, n, pIdx)
if (k == p) return A[p]
elif (k < p)
return select(A[1...p-1], k)
elif (k > p)
return select(A[p+1...n], k)For this, we recurse only once compared to twice with Quick Sort. For better results, a paranoid select function can be implemented that repeatedly paritions until p > n/10 and p < 9n/10. This gives the following recurrence:
E[T(n)] = E[T(9n/10)] + E[#partition](n)
≤ E[T(9n/10)] + 2n
≤ 2n + 2n(9/10) + (9/10)E[T(9n/10)]
≤ 2n + 2n(9/10) + 2n(9/10)^2 + ...
≤ O(n)
where n is the cost of partitioning