Vorlesung Informatik 2 - Teil B: Theorie
2.7 Quick-Sort
1960 von Charles Hoare gefunden.
Divide and Conquer Verfahren:
- Wähle ein Pivot Element p, z.B. das mittlere im Array,
- suche von links das erste Element ai mit ai>p,
- suche von rechts das erste Element aj mit aj<p ,
- vertausche ai mit aj ,inkrementiere i und dekrementiere j ,
- wiederhole Schritte 2-4 bi bis j<=i ist.
Jetzt gilt: alles links von p ist kleiner als p, alles rechts größer als p. - Wiederhole Schritte 1-5 rekursiv für den linken und rechten Teil.
Pseudo-Code:
quickSort(a, start, end){ // sortiert a[start,end]
i=start, j=end, p=a[(start+end)/2];
while(i<=j){
while(a[i]<p) i++;
while(a[j]>p) j--; if(i<=j) tausche(a,i++,j--); } if(start<j) quickSort(a,start,j); if(i<end) quickSort(a,i,end); }
Getauscht wird über die maximal mögliche Distanz.
Da in jedem Schritt die Datenmenge um die hälfte reduziert wird, ergibt sich die Komplexität O(N logN).
Die Pivot-Suche ist ein wichtiger Schritt, einfach nur die Mitte zu nehmen wie im Pseudo-Code Beispiel führt zu O(N2), wenn die Daten umgekehrt sortiert sind. Eine bessere Strategie ist, das erste, letzte und mittlere Array-Element zu vergleichen und davon das mittlere zu nehmen. Eine andere Strategie ist die zufällige Wahl von p.
Quick-Sort ist in-situ aber nicht stabil, es existieren aber stabile Varianten, z.B. auf GitHub.
Die Java Methode Arrays.sort(int[] a) implementiert Quick-Sort.