Quicksort – Funktionsweise

Quicksort beruht auf dem Divide & Conquer Prinzip.

Am Anfang sei die Liste unsortiert. Man wähle ein Pivotelement, vorteilhaft das erste in der Liste/ im Array. Danach durchsuche man die restliche Folge von Links bis ein Element a[i]>Pivotelement gefunden wird, oder der Rechte Rand erreicht wird. Dann durchsuche man die Folge von Rechts bis ein Element a[j]<Pivotelement gefunden wurde. Fall i < j vertausche man die zwei Folgenelemente und wiederhohle den obigen Schritt. Ist jedoch i≥j, vertausche man a[j] mit dem Pivotelement. An der Stelle wo das Pivotelement nu eingefügt wurde wird die Folge in die Teilfolgen S1 = (a[1],…,a[j-1]) und S2=(a[j+1],…,a[n]). Die entstandenen Teilfolgen werden Rekursiv, Analog zu der ersten Folge, behandelt.

Bemerke:

Der Vertauschungsprozess ist abhängig von der Wahl des Pivotelements.

Wählen wir zum Beispiel immer das letzte Folgenelement als Pivotelement, und suche man von links ein a[i] mit a[i]>k (oder das Ende) und von rechts ein a[j]<k (oder das Ende), und stoße man dann auf den Fall j≤i, so vertausche man nun nichtmehr das Pivotelement mit a[j] sondern mit a[i]!.

Es ist jedoch allgemein empfehlenswert das erste Folgenelement als Pivotelement zu wählen.

Worst Case:

Wenn man immer das letzte Folgenelement als Pivotelement nimt, wird in jeden Iterationsschritt nur ein Element abgespalten. Man muss also alle verbleibenden Elemente vergleichen. Dadurch entsteht ein hoher zeitlicher Aufwand. Die Perfomance des Quicksort-Algorithmus hängt von der Beschaffenheit der zu sortierenden Zahlenfolge un der Wahl des Pivotelements ab.