|
Hierbei handelt es sich um eine Alternative zu Variante 1. Die Idee ist einfach: Realisiert man die Suche des größten
Elementes etwas anders, so ist eine Parallelisierung möglich.
| Variante | 2.a (halbiterativ) |
|---|
| Typ | alternativ |
|---|
| Eigenschaften | halbiterativ, in-place, instabil, parallelisierbar |
|---|
| Datenstrukturen | Felder |
|---|
| Speicher | Ω(logn) | Θ(logn) | Ο(logn) |
|---|
| Laufzeit (p) | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
|---|
| 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:= max(A, l, i);
exchange(A[q], A[i]);
}
}
int max(field A, int l, int r) {
if (r > l) then {
int q = (l+r) div 2;
do parallel {
p:= max(A, l , q);
q:= max(A, q+1, r);
}
if (A[p] > A[q])) {
q:= p;
}
} else {
q:= l;
}
return q;
}
| |
| Variante | 2.b (rekursiv) |
|---|
| Typ | alternativ |
|---|
| Eigenschaften | rekursiv, in-place, instabil, parallelisierbar |
|---|
| Datenstrukturen | Felder |
|---|
| Speicher | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit (p) | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
|---|
| 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 l, int r) {
...
}
| |
Selectsort, Variante 2
|