Hierbei handelt es sich um stark verbesserte Variante. Die Idee ist einfach: Es soll "gleichzeitig" das größte und
kleinste Element gesucht werden. Das geht schneller.
Analog zu Bubblesort (Variante 2 und 4) sind auch hier einige zusätzliche Optimierungen möglich.
Eine rekrusive Lösung (Variante 3.b) wäre ebenfalls realisierbar.
Variante | 3.a (iterativ) |
Typ | optimiert |
Eigenschaften | iterativ, in-place, instabil, parallelisierbar |
Datenstrukturen | Felder |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit (p) | Ω(n²) | Θ(n²) | Ο(n²) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | 3/8*n² | 3/8*n² | 3/8*n² |
Vertauschungen | 0 | 1/8*n² | 3/8*n² |
shakersort(field A, int l, int r) {
while (l < r) do {
q:= split(A, l, r);
do parallel {
{ shaker2(A, l , q);l++; }
{ shaker1(A, q+1, r);r--; }
}
}
}
int split(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]);
}
}
return r-q;
}
shaker1(field A, int l, int r) {
for j:=l to r-1 do {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
}
}
}
shaker2(field A, int l, int r) {
for j:=r-1 downto l do {
if (A[j] > A[j+1]) then {
exchange(A[j], A[j+1]);
}
}
}
| |
Shakersort, Variante 3
|