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.
In more detail
A boundary index tracks where the "smaller than pivot" region ends; when the sweep finds a smaller item it swaps it to the boundary and advances it. At the end the pivot is swapped into the boundary, its final place. It is easy to get right but performs badly on inputs with many equal keys.
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.
- pivot — The item quicksort chooses to split a list around: smaller items go to its left and larger ones to its right.
- in-place algorithm — An algorithm that rearranges its input within the input's own memory, using only a constant amount of extra space.
Taught in
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers