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
|