Hierbei handelt es sich um eine verbesserte Variante. Aufgrund dieser Verbesserung ist eine iterative Realisierung nichtmehr möglich.
Die Idee ist analog zu Variante 3 von Bubblesort.
Variante | 3.a (halbiterativ) |
Typ | optimiert |
Eigenschaften | halbiterativ, in-place, instabil, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(n) | Ο(n) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/4 | n²/2 |
Vertauschungen | 0 | n | n |
selectsort(field A, int l, int r) {
while (l < r) do {
r:= select(A, l, r);
}
}
int select(field A, int l, int r) {
for i:=l+1 to r do {
if (A[i] > A[l]) then {
r:= select(A, i, r);
i--;
}
}
exchange(A[l], A[r]);
return r-1;
}
| |
Variante | 3.b (rekursiv) |
Typ | optimiert |
Eigenschaften | rekursiv, in-place, instabil, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n) | Θ(n²) | Ο(n²) |
Vergleiche | n | n²/4 | n²/2 |
Vertauschungen | 0 | n | n |
selectsort(field A, int l, int r) {
if (l < r) then {
r:= select(A, l, l+1, r);
selectsort(A, l, r);
}
}
int select(field A, int q, int l, int r) {
if (l <= r) then {
if (A[l] > A[q]) then {
r:= select(A, l, l+1, r);
r:= select(A, q, l, r);
} else {
r:= select(A, q, l+1, r);
}
return r;
} else {
exchange(A[q], A[r]);
return r-1;
}
}
| |
Selectsort, Variante 3
|