# Quicksort Algorithm

Jump to navigation
Jump to search

The Quicksort Algorithm is a randomized divide and conquer algorithm sorting algorithm.

**Context:**- It can be implemented by a Quicksort-based Sorting System.

**Example(s):**

function qsort!(a,lo,hi) i, j = lo, hi while i < hi pivot = a[(lo+hi)>>>1] while i <= j while a[i] < pivot; i = i+1; end while a[j] > pivot; j = j-1; end if i <= j a[i], a[j] = a[j], a[i] i, j = i+1, j-1 end end if lo < j; qsort!(a,lo,j); end lo, j = i, hi end return a end

**Counter-Example(s):****See:**Las Vegas Algorithm.

## References

### 2012

- http://en.wikipedia.org/wiki/Quicksort
- QUOTE: '
*Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes [math]\displaystyle{ {O}(n\log n) }[/math] comparisons to sort*n items. In the worst case, it makes [math]\displaystyle{ {O}(n^2) }[/math] comparisons, though this behavior is rare. Quicksort is often faster in practice than other [math]\displaystyle{ {O}(n\log n) }[/math] algorithms.^{[1]}Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only [math]\displaystyle{ {O}(\log n) }[/math] additional space.^{[2]}Quicksort (also known as "partition-exchange sort") is a comparison sort and, in efficient implementations, is not a stable sort.

- QUOTE: '

- ↑ S. S. Skiena, The Algorithm Design Manual, Second Edition, Springer, 2008, p. 129
- ↑ "Data structures and algorithm: Quicksort". Auckland University. http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort1a.html.

### 2017

function qsort!(a,lo,hi) i, j = lo, hi while i < hi pivot = a[(lo+hi)>>>1] while i <= j while a[i] < pivot; i = i+1; end while a[j] > pivot; j = j-1; end if i <= j a[i], a[j] = a[j], a[i] i, j = i+1, j-1 end end if lo < j; qsort!(a,lo,j); end lo, j = i, hi end return a end

### 1962

- (Hoare, 1962) ⇒ C. A. R. Hoare. (1962). “Quicksort.” In: The Computer Journal 1962 5(1) doi:10.1093/comjnl/5.1.10
- ABSTRACT: A description is given of a new method of sorting in the random-access store of a computer. The method compares very favourably with other known methods in speed, in economy of storage, and in ease of programming. Certain refinements of the method, which may be useful in the optimization of inner loops, are described in the second part of the paper.