Quicksort algorithm
Algoritmo quicksort
- Date
- 1959 · confidence high
- Place
- Moscow, Russia
- Credited to
- Tony Hoare
- Field
- Knowledge & symbols
What it is
As a visiting student in Moscow, Tony Hoare devises the partition-based ('divide and conquer') sorting algorithm while needing to alphabetise Russian words for a machine-translation project.
Hoare published the theoretical analysis in 1962 (The Computer Journal) and an improved ALGOL version in 1961.
What it led to
- Most widely used sorting algorithm in programming libraries
- Development of other partition and selection algorithms
- Analysis of average-case algorithmic complexity