Quicksort
Not met yet
Quicksort picks one item as the pivot and splits the pile into three: smaller than the pivot, the same, and bigger. The smaller and bigger piles are sorted the same way, and the three are joined in order. Forget the pile of the same and you lose every copy of the pivot but one. With a decent pivot each split roughly halves the work, so it's O(n log n) on average; a bad pivot every time, like the first item of a pile already in order, makes it O(n²).
Try it
main.pyOutput
Press Run and what your program prints shows up here.
Easy to get wrong
- Thinks items equal to the pivot still land in one of the piles when the split only keeps lighter and heavier ones.
- Thinks splitting round a pivot also puts each of the smaller piles in order.
- Thinks quicksort is at its fastest on a list that is already sorted, whatever pivot it picks.