Randomized Algorithms
Use random choices so no single input is always bad (Las Vegas) or accept a small error chance (Monte Carlo).
More Sorts: Random pivots on the worst input for a fixed one
Indices 0 to 11, depth 0. The seed picks index 7, holding 8, as the pivot, and it is swapped to the end so the ordinary partition can run.
Cost
- Space
- O(1)
Before this
Related
Taught by the same lesson
More Sorts covers these too, in the same run.