|
Hierbei handelt es sich um die Original-Variante.
Bei der Laufzeitabschätzung wird die Zahl 2.71 erwähnt. Diese Zahl ist gerundet und steht für "1.5log3".
| Variante | 1 |
|---|
| Typ | standard |
|---|
| Eigenschaften | rekursiv, in-place, instabil, 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 (A[l] > A[r]) then {
exchange(A[l], A[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);
}
}
| |
Tripplesort, Variante 1
|