|
Hierbei handelt es sich um das Grundgerüst eines temporären Indexfeldes. Das Prinzip wird im Folgenden an der Standardvariante von Bubblesort demonstriert.
Eine rekursive Realisierung (Variante 1.b) ist möglich.
| Variante | 1.a (iterativ) |
|---|
| Typ | standard, Beispiel |
|---|
| Eigenschaften | iterativ, in-place, stabil, nicht parallelisierbar |
|---|
| Datenstrukturen | Felder |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n²/2 | n²/2 | n²/2 |
|---|
| Vertauschungen | 0 | n | n |
|---|
tepifsort(field A, int l, int r) {
for i:= l to r do {
B[0][i]:= i;
}
bubblesort(B[0], A, l, r);
for i:= l to r do {
B[1][B[0][i]]:= i;
}
for i:= l to r-1 do {
s:= B[0][i];
t:= B[1][i];
exchange(A[s], A[i]);
B[0][t]:= s;
B[1][s]:= t;
}
}
bubblesort(int[] B, field A, int l, int r) {
for i:=r downto l+1 do {
for j:=l to i-1 do {
if (A[B[j]] > A[B[j+1]]) then {
exchange(B[j], B[j+1]);
}
}
}
}
| |
Tepifsort, Variante 1
|