Hierbei handelt es sich um eine alternative Variante, die besonders für Listen geeignet ist. Diese Variante ist
realisierbar, wenn von Anfang an klar ist, daß die Daten mit diesem Verfahren sortiert werden sollen.
Eine rekursive Realisierung (Variante 2.b) ist möglich.
Diese Variante wäre mit ein paar Änderungen in resolve parallelisierbar. Auf die asymptotische Laufzeit hätte das aber keinen Einfluß.
Variante | 2.a (halbrekursiv) |
Typ | alternativ |
Eigenschaften | halbrekursiv, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | einfachverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
Vergleiche | n(logn-1.1) | n(logn-1.1) | n(logn-0.7) |
Verschiebungen | 0 | n | n |
avlsort(listele first, listele last) {
root := first;
lastnext:= last.next;
for ele:=first.next to last do {
ele.prev:= null;
ele.next:= null;
root:= insert(root, ele);
}
lastnext.prev:= resolve(root, first.prev);
lastnext.prev.next:= lastnext;
}
listele insert(listele current, listele element) {
if (element < current) then {
if (current.prev <> null) then {
current.prev:= insert(A, current.prev, element);
pbal := -pbal;
} else {
current.prev:= element;
pbal := -1;
}
} else {
if (current.next <> null) then {
current.next:= insert(A, current.next, element);
} else {
current.next:= element;
pbal := +1;
}
}
return balance(current, pbal);
}
listele resolve(node current, listele prev) {
if (current <> null) then {
prev:= resolve(current.prev, prev);
prev.next:= current;
current.prev:= prev;
return resolve(current.next, current);
} else {
return prev;
}
}
listele rrot(node a) {
...
}
listele lrot(node a) {
...
}
listele balance(node a, int bal) {
...
}
| |
Avlsort, Variante 2
|