|
Hierbei handelt es sich um die Original-Variante.
Eine rekursive Realisierung (Variante 1.b) ist möglich.
| Variante | 1.a (iterativ) |
|---|
| Typ | standard |
|---|
| Eigenschaften | iterativ, parallelisierbar |
|---|
| Datenstrukturen | Felder |
|---|
| Speicher | Ω(1) | Θ(1) | Ο(1) |
|---|
| Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(n) | Θ(n) | Ο(n) |
|---|
| Vergleiche | 3/2n | 3/2n | 3/2n |
|---|
{int,int} mmsearch(field A, int l, int r) {
q:= (r-l+1)/2;
for i:= l+q to r do parallel {
if (A[i-q] > A[i]) then {
exchange(A[i-q], A[i]);
}
}
do parallel {
a:= selectmin(A, l, r-q);
b:= selectmax(A, r-q+1, r);
}
return {a,b}
}
int selectmin(field A, int l, int r) {
q:= l;
for j:=l+1 to r do {
if (A[j] < A[q]) then {
q:= j;
}
}
return q;
}
int selectmax(field A, int l, int r) {
q:= l;
for j:=l+1 to r do {
if (A[j] > A[q]) then {
q:= j;
}
}
return q;
}
| |
|