Hierbei handelt es sich um die Original-Variante.
Es ist zu empfehlen, die Suche des i. größten Elementes mit der des i. kleinsten Elementes zu verbinden und die günstigere von beiden auszuwählen.
Eine rekursive Realisierung (Variante 1.b) ist möglich.
Variante | 1.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(i*n) | Θ(i*n) | Ο(i*n) |
Vergleiche | i*(n-i/2) | i*(n-i/2) | i*(n-i/2) |
int selectsearch(field A, int l, int r, int i) {
for k:=r downto r-i+1 do {
q:= l;
for j:=l+1 to k do {
if (A[j] > A[q]) then {
q:= j;
}
}
exchange(A[q], A[k]);
}
return r-i+1;
}
| |
|