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.
In more detail
Quicksort averages O(n log n) and sorts in place, which makes it fast in practice. A consistently bad pivot, such as the last element of already sorted input, makes it O(n^2). It is not stable by default.
Related terms
- pivot — The item quicksort chooses to split a list around: smaller items go to its left and larger ones to its right.
- 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.
- divide and conquer — A problem-solving technique that splits a problem into independent smaller pieces, solves each recursively, and combines their answers.
- in-place algorithm — An algorithm that rearranges its input within the input's own memory, using only a constant amount of extra space.
- average case — The typical cost of an algorithm averaged over the inputs you expect, which requires a model of how inputs are distributed.
Taught in
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers