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
|