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