Randomized Algorithms
Use random choices so no single input is always bad (Las Vegas) or accept a small error chance (Monte Carlo).
Decision · step 2 of 41More 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.
What you will see
Randomized quick sort's pivot choices differ per seed; the depth stays small on every run.
Cost
| Space | O(1) |
|---|
How you work with it here
play it through, step one change at a time, compare two runs.
Screen readers: Each paradigm lesson is narrated as the characteristic loop it performs; the comparison view is available as a table.
Reduced motion: Side-by-side panes update in place.
Before this
Taught by the same lesson
More Sorts covers these too, in the same run.