|
Hierbei handelt es sich um eine alternative Variante, die besonders für Listen geeignet ist.
Auch hier ist die Idee einfach: Da bei Listen Verschiebungen billiger als Vertauschungen sind,
wird der Algorithmus dem entsprechend angepaßt.
Analog zur Variante 1 kann nun ebenfalls eine entsprechende Variante 2 und 3 entwickelt werden.
| Variante | 4.a (iterativ) |
|---|
| Typ | alternativ |
|---|
| Eigenschaften | iterativ, in-place, instabil, nicht parallelisierbar |
|---|
| Datenstrukturen | einfachverkettete Listen, Felder |
|---|
| Speicher | Ω(1) | Θ(1) | Ο(1) |
|---|
| Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n²/2 | n²/2 | n²/2 |
|---|
| Verschiebungen | 0 | n | n |
|---|
selectsort(field A, int l, int r) {
for i:=r downto l+1 do {
q:= l;
for j:=l to i-1 do {
if (A[j+1] > A[q]) then {
q:= j+1;
}
}
move(A[q], A[i]);
}
}
| |
| Variante | 4.b (rekursiv) |
|---|
| Typ | alternativ |
|---|
| Eigenschaften | rekursiv, in-place, instabil, nicht parallelisierbar |
|---|
| Datenstrukturen | einfachverkettete Listen, Felder |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n²/2 | n²/2 | n²/2 |
|---|
| Verschiebungen | 0 | n | n |
|---|
selectsort(field A, int l, int r) {
if (l < r) then {
q:= max(A, l, l+1, r);
move(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 {
q:= l;
}
return max(A, q, l+1, r);
} else {
return q;
}
}
| |
Selectsort, Variante 4
|