Hierbei handelt es sich um eine alternative verbesserte Variante. Die Idee folgt aus der Bemerkung zu Variante 1.
Variante | 3.a (iterativ) |
Typ | standard, trinär (3-när) |
Eigenschaften | iterativ, in-place, instabil, nicht parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(n) | Θ(nlogn) | Ο(nlogn) |
Vergleiche | 4n | n(1.9logn-2.4) | 1.9nlogn |
Vertauschungen | n | nlogn/1.6 | nlogn/1.2 |
heapsort(field A, int l, int r) {
buildheap(A, l, r);
for i:=r downto l+1 do {
exchange(A[l], A[i]);
heapify(A, l, l, i-1);
}
}
buildheap(field A, int l, int r) {
for i:= (r-l-1) div 3 downto 0 do {
heapify(A, l, l+i, r);
}
}
heapify(field A, int l, int q, int r) {
for ever do {
largest:= l+3*(q-l)+1;
if (largest <= r) then {
p:= largest+1;
if (p <= r) and (A[p] > A[largest]) then {
largest:= p;
}
if (p < r) and (A[p+1] > A[largest]) then {
largest:= p+1;
}
if (A[largest] > A[q]) then {
exchange(A[largest], A[q]);
q:= largest;
} else {
return;
}
} else {
return;
}
}
}
| |
Variante | 2.b (halbiterativ) |
Typ | standard, trinär (3-när) |
Eigenschaften | halbiterativ, in-place, instabil, nicht parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(1) | Θ(logn) | Ο(logn) |
Laufzeit | Ω(n) | Θ(nlogn) | Ο(nlogn) |
Vergleiche | 4n | n(1.9logn-2.4) | 1.9nlogn |
Vertauschungen | n | nlogn/1.6 | nlogn/1.2 |
heapsort(field A, int l, int r) {
buildheap(A, l, r);
for i:=r downto l+1 do {
exchange(A[l], A[i]);
heapify(A, l, l, i-1);
}
}
buildheap(field A, int l, int r) {
for i:= (r-l-1) div 2 downto 0 do {
heapify(A, l, l+i, r);
}
}
heapify(field A, int l, int q, int r) {
largest:= l+3*(q-l)+1;
if (largest <= r) then {
p:= largest+1;
if (p <= r) and (A[p] > A[largest]) then {
largest:= p;
}
if (p < r) and (A[p+1] > A[largest]) then {
largest:= p+1;
}
if (A[largest] > A[q]) then {
exchange(A[largest], A[q]);
heapify(A, l, largest, r);
}
}
}
| |
Heapsort, Variante 3
|