pivot
The item quicksort chooses to split a list around: smaller items go to its left and larger ones to its right.
In more detail
After partitioning, the pivot is in its final sorted position. A pivot near the median splits the work evenly; one near the minimum or maximum leaves one side almost empty and drives quicksort towards O(n^2). Choosing the pivot at random makes that worst case very unlikely for any input.
Related terms
- quicksort — A divide-and-conquer sort that picks a pivot, partitions the items into those smaller and larger than it, and sorts each part recursively.
- Lomuto partition — A simple way to partition for quicksort: use the last element as the pivot and sweep left to right, swapping smaller items to the front.
Taught in
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers