Quicksort, Variante 2 (Tri-Median)

Hierbei handelt es sich um eine leicht verbesserte Variante. Durch eine sorgfältigere Auswahl des Pivotelementes in partition (Tri-Median-Methode) kann die Chance eines worst-case-Falles stark minimiert werden. Die Laufzeit im mittleren Fall wird allerdings etwas schlechter.

Eine rekursive Realisierung (Variante 2.b) ist analog zu Variante 1 möglich.

Variante 2.a (halbrekursiv)
Typ optimiert
Eigenschaften halbrekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder
Speicher Ω(logn) Θ(logn) Ο(n)
Laufzeit (p) Ω(n) Θ(n) Ο(n²)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(n²)
Vergleiche nlogn 1.5nlogn n²/2
Vertauschungen 0 nlogn/3.9 n²/4

quicksort(field A, int l, int r) {
  if (l < r) then {
    q:= partition(A, l, r);
    do parallel {
      quicksort(A, l, q);
      quicksort(A, q+1, r);
    }
  }
}

int partition(field A, int l, int r) {
  i:= (l+r) div 2;
  if (A[i] > A[r]) exchange(A[i], A[r]);
  if (A[l] > A[r]) exchange(A[l], A[r]);
  if (A[l] > A[i]) exchange(A[l], A[i]);
  x:= A[i];
  i:= l-1;
  j:= r+1;
  while true do {
    do { j--; } while (A[j] > x);
    do { i++; } while (A[i] < x);
    if (i < j) then {
      exchange(A[i], A[j]);
    } else {
      return j;
    }
  }
}


Quicksort, Variante 2