# 32.4 Summary

What can we do to avoid the worst case runtime of

$\theta(N^2)$

for Quicksort? - 1.Randomness: pick a random pivot point, shuffle items before sorting
- 2.Smarter Pivot Selection: constant time pivot pick (ex: pick a few and then choose the best out of them), linear time pivot pick like (ex: median)
- 3.Introspection: switch to a different sort if current sort hits recursion depth threshold

Quicksort vs. Mergesort

- Mergesort is faster than Quicksort L3S (leftmost pivot, 3-scan partition) and QuickSort PickTH (median pivot, Tony Hoare partition)
- Quicksort LTHS (leftmost pivot, Tony Hoare partition) is faster than Mergesort!
- Tony Hoare's partitioning:
- two pointers, one at each end of the items array, walking towards each other
- left pointer hates larger or equal items, right pointer hates smaller or equal items
- swapping anything they don’t like; stop when the two pointers cross each other
- new pivot = Item at right pointer.

Quick select helps us quickly find the median with partitioning. Median of an length n array will be around index n /2.

- 1.Initialize array with the leftmost item as the pivot.
- 2.Partition around pivot.
- 3.Partition the subproblem. Repeat the process.
- 4.Stop when the pivot is at the median index.

Expected runtime:

$\theta(N)$

. Worst case runtime (when array is in sorted order): $\theta(N^2)$

.Stability: A sort is stable if the order of equivalent elements is preserved.

Optimizations:

- Adaptiveness - sort that exploits the existing order of the array.
- Switch to Insertion Sort - when a subproblem reaches size 15 or lower
- Exploit restrictions on set of keys
- Switch from QuickSort - if the recursion goes too deep

Last modified 10mo ago