Startseite
Informatik
Algorithmen
Sortieren
BucketSort
RadixSort
QuickSort
MergeSort
HeapSort
BubbleSort
DRUCK
2004
2005
2006
2007
2008
2009
ShakerSort
SelectionSort
InsertionSort
SlowSort
BogoSort
Komprimieren
Suchen
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
ShakerSort
Ein verbesserter BubbleSort, aber immer noch ineffizient, ist der ShakerSort!
Ein verbesserter BubbleSort, aber immer noch ineffizient, ist der ShakerSort!
Einführung
Theorie: ShakerSort
Definition
ShakerSort:
Man kann zur Beschleunigung einige Verbesserungen am
BubbleSort
anbringen.
Beispielsweise weist der BubbleSort eine Besonderheit auf:
ein falsch platziertes Element am unteren Ende, wie das
a
in dem Array
dcab,
gelangt in nur einem Durchlauf an seinen richtigen Platz, während ein falsch stehendes Element am oberen Ende
(wie das d)
sehr langsam zum richtigen Platz voranschreitet.
Statt das Array immer in derselben Richtung zu durchlaufen
(unidirektional),
könnte die Richtung nach jedem Durchgang umgekehrt werden
(bidirektional).
Damit bewegen sich Elemente, die weit von ihrer richtigen Position entfernt sind, mit größerer Geschwindigkeit auf diese zu.
Die hier gezeigte Version des BubbleSort wird ShakerSort (auch CocktailSort, Shearsort oder bidirektionales Bubblesort) genannt, weil er sich wie der Schüttelbecher eines Barmixers (Cocktailbecher) über den Array bewegt. [PROFC]
Die hier gezeigte Version des BubbleSort wird ShakerSort (auch CocktailSort, Shearsort oder bidirektionales Bubblesort) genannt, weil er sich wie der Schüttelbecher eines Barmixers (Cocktailbecher) über den Array bewegt. [PROFC]
Komplexität
Obgleich der Shaker den BubbleSort verbessert, ist seine Ausführungszeit immer noch von der Größenordnung
O(n²),
denn die Anzahl der Vergleiche bleibt ungeändert und auch die Anzahl der Vertauschungen ist nur um eine relativ kleine
Konstante zurückgegangen.
[PROFC]
Konkretes Zahlenbeispiel
Dabei sei nun
[6,2,4,7,3,5,1]
die zu sortierende Liste:
[6,2,4,7,3,5,1][2,4,6,3,5,1,7][1,2,4,6,3,5,7][1,2,4,3,5,6,7][1,2,3,4,5,6,7]
1
an den Listenanfang zu propagieren,
hätte der
BubbleSort
bei diesem Beispiel 7 Durchläufe benötigt.
Nach dem 2. Durchlauf stehen hier die größte und die kleinste Zahl gegebener Liste an den richtigen Positionen.
Implementierung
Implementierung des ShakerSort
Implementierung mit Delphi
unit UShakerSort;
interface
procedure ShakerSort(var A: array of Integer);
implementation
procedure ShakerSort(var A: array of Integer);
procedure Swap(var X, Y: Integer);
var
Swp: Integer;
begin
Swp := X;
X := Y;
Y := Swp;
end;
var
Size, Half: Integer;
I, J: Integer;
begin
Size := (High(A) - Low(A)) + 1;
Half := Size div 2;
for I := 1 to Half do
begin
for J := Low(A) to High(A) - I do
if A[J] > A[J + 1] then Swap(A[J], A[J + 1]);
for J := High(A) downto Low(A) + I do
if A[J - 1] > A[J] then Swap(A[J - 1], A[J]);
end;
end;
end.
Implementierung mit C++
#include <stdio.h>
#include <stdlib.h>
/* Sortiert die ersten n Elemente des int-Arrays v */
void shakersort(int v[], int n) {
int lower = 1;
int higher = n - 1;
int lastswap = n - 1;
// down up down up down up down up down up down ...
do {
// bubble down
for (int i = higher; i >= lower; i--) {
if (v[i-1] > v[i]) {
int swp = v[i-1];
v[i-1] = v[i];
v[i] = swp;
lastswap = i;
}
}
lower = lastswap + 1;
// bubble up
for (int i = lower; i <= higher; i++) {
if (v[i-1] > v[i]) {
int swp = v[i-1];
v[i-1] = v[i];
v[i] = swp;
lastswap = i;
}
}
higher = lastswap - 1;
} while (lower <= higher);
}
// Kleiner Test: Lass shaken!
int main() {
int values[] = {25, 13, 19, 31, 11, 99, 21, 17};
int count = sizeof(values) / sizeof(*values);
// Ausgabe der Werte (vorher)
for (int i = 0; i < count; i++) printf("%5d", values[i]);
printf("\n");
// Sortiere alle (count!) Elemente von values
shakersort(values, count);
// Ausgabe der Werte (nachher)
for (int i = 0; i < count; i++) printf("%5d", values[i]);
printf("\n");
system("PAUSE");
return 0;
}
Implementierung mit Perl
#!/usr/bin/perl
sub ShakerSort {
my ($comp,@list) = @_;
for (my $j=0; $j<=int(($#list)/2); $j++) {
# shaker up
for (my $i=0; $i<($#list-$j); $i++) {
if (&$comp($list[$i+1],$list[$i])) {
($list[$i],$list[$i+1]) = ($list[$i+1],$list[$i]);
}; # if $list...
}; # for $i...
# shaker down
for (my $i=$#list; $i>$j; $i--) {
if (&$comp($list[$i],$list[$i-1])) {
($list[$i-1],$list[$i]) = ($list[$i],$list[$i-1]);
}; # if $list...
}; # for $i...
}; # for $j...
return @list;
};
# --- Anwendungsbeispiel ---
# Vergleichsfunktionen
my $numAsc = sub {return $_[0] < $_[1];};
my $numDesc = sub {return $_[0] > $_[1];};
@A = (4,2,9,3,0,5,1,8,6,7);
@B = &ShakerSort($numAsc,@A);
@C = &ShakerSort($numDesc,@A);
print "# @A (unsortiert)\n";
print "#\n";
print "# @B (aufsteigend; asc)\n";
print "# @C (absteigend; desc)\n";
# --- Besondere Anwendungsbeispiele ---
@X1 = (4,2,9,3,0);
@X2 = (8,6,7);
@X3 = (5,1);
@X = &ShakerSort($numAsc, @X1,@X2,@X3);
@Y = &ShakerSort($numAsc, 4,2,9,3,0,5,1,8,6,7);
print "#\n";
print "# @X (3 Arrays sortiert)\n";
print "# @Y (Argumente sortiert)\n";
exit;
Quellenangabe
-
[PROFC]