Objective
Watch quick sort pick a pivot, partition the array and recurse, and see how the choice of pivot decides its real-world cost.
The idea
Quick sort partitions around a pivot, then recurses on both sides. Run it on the same data with different pivots and compare the work.
Try this
- 1Run quick sort on a random array and count partitions.
- 2Feed it an already-sorted array with a bad pivot.
- 3Use the median pivot and watch the recursion balance.
- 4Compare average vs worst-case comparison counts.
Watch for
- Each partition puts the pivot in its final position.
- A good pivot splits the array roughly in half.
- The worst case is already-sorted data with a naive pivot.
- Expected cost is O(n log n); worst case is O(n^2).