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
|