Quicksort Algorithm
(Redirected from 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: '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]
- ↑ 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.