Hierbei handelt es sich um die Original-Variante.
(*) Analog zur Variante 2 von Selectsort kann hier eine Alternative zur Zählung der kleineren Elemente entwickelt werden, die dann parallelisierbar wäre.
Eine rekursive Realisierung (Variante 1.b) ist möglich.
Variante | 1.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, in-place, instabil, parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit (p) | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | 0.75*n² | n² |
Vertauschungen | 0 | n | n |
plaselsort(field A, int l, int r) {
for i:=l to r+1 do {
B[i]:= 0;
}
i:= l;
do {
q:= i; // (*)
for j:=i+1 to r do { // (*)
if (A[j] < A[i]) then { // (*)
q++; // (*)
} // (*)
} // (*)
p:= q + B[q];
exchange(A[i], A[p]);
B[q]++;
if (p > q) B[p]++;
while (B[i] > 0) do { i++; }
} while (i < r);
}
| |
Plaselsort, Variante 1
|