Vorlesung Informatik 2 - Teil B: Theorie

2.7 Quick-Sort

1960 von Charles Hoare gefunden.

Divide and Conquer Verfahren:

  1. Wähle ein Pivot Element p, z.B. das mittlere im Array,
  2. suche von links das erste Element ai mit ai>p,
  3. suche von rechts das erste Element aj mit aj<p ,
  4. vertausche ai mit aj ,inkrementiere i und dekrementiere j ,
  5. 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.
  6. 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.


Lehrvideo  (YouTube)