Hierbei handelt es sich um die Original-Variante.
Variante | 1.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, in-place, instabil, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Vertauschungen | 0 | n | n |
selectsort(field A, int l, int r) {
for i:=r downto l+1 do {
q:= l;
for j:=l+1 to i do {
if (A[j] > A[q]) then {
q:= j;
}
}
exchange(A[q], A[i]);
}
}
| |
Variante | 1.b (rekursiv) |
Typ | standard |
Eigenschaften | rekursiv, in-place, stabil, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Vertauschungen | 0 | n | n |
selectsort(field A, int l, int r) {
if (l < r) then {
q:= max(A, l, l+1, r);
exchange(A[q], A[r]);
selectsort(A, l, r-1);
}
}
int max(field A, int q, int l, int r) {
if (l <= r) then {
if (A[l] > A[q]) then {
return max(A, l, l+1, r);
} else {
return max(A, q, l+1, r);
}
} else {
return q;
}
}
| |
Selectsort, Variante 1
|