Quicksort

Schneller, rekursiver Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (engl. Divide and conquer) arbeitet.

QuickSort wählt ein Element aus der zu sortierenden Liste aus ("Pivotelement") und zerlegt die Liste in zwei Teillisten, von denen die eine alle Elemente enthält, die größer sind als das Pivotelement, die andere den Rest. Entsprechend werden auch die Teillisten zerlegt (Rekursion) und, sobald nur noch Listen mit einem Element vorhanden sind, wieder zusammengesetzt.

QuickSort liegt im worst case (schlimmsten Fall) in der Aufwandsklasse O(n²), im Mittel in der Aufwandsklasse O(n * log n).