|
Hierbei handelt es sich um eine vereinfachte Variante. Die Idee ist einfach:
Der Algorithmus kann stark vereinfacht werden, wenn alle Elemente eindeutig platziert werden können, d.h. es gilt
immer (A[i] <> A[j]) für alle i <> j.
(*) Analog zur Variante 2 von Selectsort kann hier eine Alternative zur Zählung der kleineren Elemente entwickelt werden, die dann parallelisierbar wäre.
| Variante | 2.a (iterativ) |
|---|
| Typ | vereinfacht |
|---|
| Eigenschaften | iterativ, in-place, instabil, parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(1) | Θ(1) | Ο(1) |
|---|
| Laufzeit (p) | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
|---|
| Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n²/2 | 1.5*n² | 2*n² |
|---|
| Vertauschungen | 0 | n | n |
|---|
plaselsort(field A, int l, int r) {
for i:= l to r-1 do {
q:= i; // (*)
for j:=i+1 to r do { // (*)
if (A[j] < A[i]) then { // (*)
q++; // (*)
} // (*)
} // (*)
exchange(A[i], A[q]);
if (q > i) then { i--; }
}
}
| |
| Variante | 2.b (rekursiv) |
|---|
| Typ | vereinfacht |
|---|
| Eigenschaften | rekursiv, in-place, instabil, nicht parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit (p) | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
|---|
| Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
|---|
| Vergleiche | n²/2 | 1.5*n² | 2*n² |
|---|
| Vertauschungen | 0 | n | n |
|---|
plaselsort(field A, int l, int r) {
if (l < r) then {
q:= l + plasel(A, l, l+1, r);
exchange(A[l], A[q]);
if (q = l) then { l++; }
plaselsort(A, l, r);
}
}
plasel(field A, int p, int l, int r) { // (*)
if (l <= r) then { // (*)
q:= plasel(A, p, l+1, r); // (*)
if (A[l] < A[p]) then { // (*)
q++; // (*)
} // (*)
return q; // (*)
} else { // (*)
return 0; // (*)
} // (*)
} // (*)
| |
Plaselsort, Variante 2
|