Quicksort

Quicksort (englisch quick ‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche arbeitet. Er wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt^[1] und seitdem von vielen Forschern verbessert. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und dass er, abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack, ohne zusätzlichen Speicherplatz auskommt.

Im Durchschnitt führt der Quicksort-Algorithmus ${\displaystyle {\mathcal {O}}(n\cdot \log(n))}$ Vergleiche durch. Im schlechtesten Fall werden ${\displaystyle {\mathcal {O}}(n^{2})}$ Vergleiche durchgeführt, was aber in der Praxis sehr selten vorkommt.^[2]

1. ↑ C. A. R. Hoare: Quicksort. In: The Computer Journal. Band 5(1), 1962, S. 10–15, doi:10.1093/comjnl/5.1.10. 
2. ↑ Steven S. Skiena: The Algorithm Design Manual. Springer, 2011, ISBN 978-1-84800-069-8, S. 129 (google.com [abgerufen am 18. Juni 2013]).