Quicksort
Efficient divide-and-conquer sorting algorithm developed by Tony Hoare.
It is a divide-and-conquer algorithm that selects a pivot element and partitions other elements into sub-arrays, making it slightly faster than merge sort and heapsort for randomized data. Quicksort remains a commonly used algorithm for sorting and is a comparison sort that can be implemented in-place.
- developed_by
- Tony Hoare
- field
- Computer science
- nationality
- British
- known_for
- Quicksort algorithm
Lore & Background
He needed to sort Russian words before looking them up in a dictionary on magnetic tape. After finding insertion sort too slow, he devised quicksort, writing the partition part in Mercury Autocode. On return to England, his boss bet a sixpence that Hoare did not know a faster algorithm than Shellsort, a bet the boss ultimately lost.
Reader's Guide
Quicksort's significance lies in its efficiency and widespread adoption. It is a divide-and-conquer algorithm that, on average, takes O(n log n) comparisons to sort n items, though in the worst case it makes O(n²) comparisons. The algorithm gained widespread use, appearing in Unix as the default library sort subroutine and lending its name to the C standard library subroutine qsort and the reference implementation of Java. Nico Lomuto's partition scheme, popularized by Bentley's book Programming Pearls and the textbook Introduction to Algorithms, is simpler but less efficient than Hoare's original scheme, doing three times more swaps on average and degrading to O(n²) when all elements are equal.
Did You Know?
- Hoare's boss bet a sixpence that Hoare did not know a faster algorithm than Shellsort, a bet the boss lost.
- The algorithm appears in Unix as the default library sort subroutine and lent its name to the C standard library subroutine qsort.
- Lomuto's partition scheme, though simpler, does three times more swaps on average than Hoare's scheme.
Frequently Asked Questions
What is Quicksort's core role in the sorting landscape?
Quicksort is a divide-and-conquer comparison sort that works by choosing a pivot element and recursively partitioning the remaining items into two sub-arrays around that pivot. It is one of the most commonly deployed general-purpose sorting algorithms in practice.
How does Quicksort stack up against merge sort and heapsort?
On typical randomized input, Quicksort tends to outperform both merge sort and heapsort by a small margin. It also has the practical advantage of being implementable in-place, so it does not demand large auxiliary memory.
Why is Quicksort still considered important in computer science?
Even more than sixty years after its publication, Quicksort remains a go-to choice for in-memory sorting because of its speed, in-place operation, and clean recursive structure. It also serves as a canonical teaching example for the divide-and-conquer paradigm in complexity theory.
More in Complexity Theory 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record