|
Hierbei handelt es sich um eine verbesserte Variante. Da Vertauschungen erst im zweielementigen
Feld nötig sind, realisieren wir diese nur in diesem Fall. Das verringert stark die Anzahl der
Vergleiche und erhöht geringfügig die Anzahl Vertauschungen. Außerdem wird diese Variante dadurch stabil.
| Variante | 2 |
|---|
| Typ | optimiert |
|---|
| Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
|---|
| Datenstrukturen | Felder |
|---|
| Speicher | Ω(logn) | Θ(logn) | Ο(logn) |
|---|
| Laufzeit | Ω(n2.71) | Θ(n2.71) | Ο(n2.71) |
|---|
| Vergleiche | ??? | ??? | ??? |
|---|
| Vertauschungen | 0 | n²/4 | n²/2 |
|---|
trippelsort(field A, int l, int r) {
if (l < r-1) then {
k:= (r-l+1) div 3;
trippelsort(A, l, r-k);
trippelsort(A, l+k, r);
trippelsort(A, l, r-k);
} else {
if (A[l] > A[r]) then {
exchange(A[l], A[r]);
}
}
}
| |
Tripplesort, Variante 2
|