Quicksort, Variante 3 (+Smallsort)

Hierbei handelt es sich um eine leicht verbesserte Variante. Die Idee ist einfach: Quicksort sortiert kleinere Teilfelder nicht optimal. Es sollte daher für kleine Teilfelder ein anderes (besseres) Verfahren verwendet werden.

Eine rekursive Realisierung (Variante 3.b) ist analog zu Variante 1 möglich. Eine Optimierung im Sinne von Variante 2 ist ebenfalls möglich.

Variante 3.a (halbrekursiv)
Typ optimiert
Eigenschaften halbrekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder, doppeltverkettete Listen
Speicher Ω(logn) Θ(logn) Ο(n)
Laufzeit (p) Ω(n) Θ(n) Ο(n²)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(n²)
Vergleiche ??? (abhängig vom Verfahren und von m)
Vertauschungen ??? (abhängig vom Verfahren und von m)
Hinweis m sollte ungefähr 10 sein

quicksort(field A, int l, int r) {
  if (r-l > m) then {
    q:= partition(A, l, r);
    do parallel {
      quicksort(A, l, q);
      quicksort(A, q+1, r);
    }
  } else {
    smallsort(A, l, r);
  }
}

int partition(field A, int l, int r) {
  x:= A[(l+r) div 2];
  i:= l-1;
  j:= r+1;
  for ever 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;
    }
  }
}

smallsort(field A, int l, int r) {
  // Ein Sortierverfahren für kleine Teilfelder
}


Quicksort, Variante 3