Schnelles Sortieren: Der Quick Sort Algorithmus

Gerade für größere Datenmengen sind die quadratischen Sortieralgorithmen ungeeignet. Eine lineare oder fast-lineare Zeitkomplexität ist hierfür besser geeignet, welche mithilfe geschickter rekursiver Verfahren erreicht werden kann. Das bekannteste Verfahren hierbei ist der Quick Sort.

Der Quick Sort arbeitet nach der Strategie: teile und herrsche. Zunächst teilt der Algorithmus die zu sortierende Reihung in eine linke und eine rechte Hälfte. Hierfür wird (zufällig) ein Pivotelement ausgewählt. Alle Elemente der Liste, welche größer als das Pivotelement sind, kommen in die rechte Hälfte und alle die kleiner sind in die linke Hälfte. Gleich große Elemente können entweder nach links oder rechts einsortiert werden.

Diese Vorgehensweise wird nun separat auf die entstandene linke und rechte Listen angewendet und sortiert diese ebenso durch Unterteilung. Daher ist der Algorithmus rekursiv. Dieses Verfahren wird so lange angewandt bis alle Elemente sortiert sind. Das ist der Fall, wenn eine Teilliste die Länge $0$ oder $1$ hat.

Im Idealfall wählt der Algorithmus ein Pivotelement aus, welches tatsächlich in der Mitte der zu sortierenden Reihung liegt. Dies ist jedoch nicht immer der Fall. Es kann passieren, dass das Pivotelement recht klein beziehungsweise recht groß ist und die Liste in eine lange und eine kurze Hälfte teilt. Im schlimmsten Fall ist jedes Pivotelement das größte (oder kleinste) Element der entsprechenden Liste und der Algorithmus benötigt $n^2$ Schritte. Im Durchschnitt wird allerdings eine Laufzeit von $n\cdot\log(n)$ erreicht.

Der Quick Sort kann hier nun mit den vorhergegangenen Verfahren verglichen werden.

Anleitung: Über die Knöpfe den Suchalgorithmus auswählen und Anzahl und Startreihenfolge der zu sortierenden Liste wählen. Mit dem Schieberegler die Geschwindigkeit der Animation steuern.

Mehr Informationen zu Algorithmen finden Sie unter (Dieker & Güting, 2018).