Quicksort, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante. Sie liefert das typische Bild eines "depth first"-Algorithmus.

Für dieses Verfahren gibt es keine vollständig iterative Realisierung.

In der Laufzeitabschätzung wird die Zahl 1.44 erwähnt. Diese Zahl ist gerundet und könnte für Wurzel aus Zwei stehen.

Variante 1.a (halbrekursiv)
Typ standard
Eigenschaften halbrekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder, doppeltverkettete Listen
Speicher Ω(logn) Θ(logn) Ο(n)
Laufzeit (p) Ω(n) Θ(n) Ο(n²)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(n²)
Vergleiche nlogn 1.44nlogn n²/2
Vertauschungen 0 nlogn/4.3 n²/4
Hinweis Bei Listen ist es in der Regel günstiger
in partition den Ausdruck "x:= A[(l+r) div 2];"
durch "x:= A[l];" zu ersetzen.

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) {
  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;
    }
  }
}

Variante 1.b (rekursiv)
Typ standard
Eigenschaften rekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder, doppeltverkettete Listen
Speicher Θ(n) Θ(n) Θ(n)
Laufzeit (p) Ω(n) Θ(n) Ο(n²)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(n²)
Vergleiche nlogn 1.44nlogn n²/2
Vertauschungen 0 nlogn/4.3 n²/4
Hinweis Bei Listen ist es in der Regel günstiger
in partition den Ausdruck "x:= A[(l+r) div 2];"
durch "x:= A[l];" zu ersetzen.

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

int partition1(field A, ele x, int i, int j) {
  j--;
  if (A[j] > x) then {
    return partition1(A, x, i, j);
  } else {
    return partition2(A, x, i, j);
  }
}

int partition2(field A, ele x, int i, int j) {
  i++;
  if (A[i] < x) then {
    return partition2(A, x, i, j);
  } else {
    if (i < j) then {
      exchange(A[i], A[j]);
      partition1(A, x, i, j);
    } else {
      return j;
    }
  }
}


Quicksort, Variante 1