imported>Trustable: linkfix

2025-08-04T13:21:12Z

linkfix

Neue Seite

Der Begriff '''Shakersort''' bezeichnet einen [[Stabilität (Sortierverfahren)|stabilen]] [[Sortierverfahren|Sortieralgorithmus]], der eine Menge von linear angeordneten Elementen (z. B. Zahlen) der Größe nach sortiert. Weitere Namen für diesen Algorithmus sind ''Cocktailsort'', ''Ripplesort'', ''Shearsort'' oder ''BiDiBubbleSort'' (bidirektionales [[Bubblesort]]).

== Prinzip ==
[[Datei:Sorting shaker sort anim.gif|mini|Animation von Shakersort, der jeweils rote Balken wird verschoben]]
Das zu sortierende Feld wird abwechselnd nach oben und nach unten durchlaufen. Dabei werden jeweils zwei benachbarte Elemente verglichen und gegebenenfalls vertauscht.

Durch diese [[Bidirektional]]ität kommt es zu einem schnelleren Absetzen von großen bzw. kleinen Elementen.
Anhand des Sortierverfahrens lässt sich auch der Name erklären, denn der Sortiervorgang erinnert an das Schütteln des Arrays oder eines Barmixers.

== Komplexität ==

Der [[Algorithmus]] besitzt eine quadratische und daher im Vergleich zu vielen anderen Sortieralgorithmen schlechte [[Worst-Case-Laufzeit]], die jedoch in der einfachen Version gleichzeitig auch der normalen Laufzeit entspricht. In der [[Informatik]] drückt man dies mittels [[Landau-Symbol]] durch <math>\textstyle\Theta(n^2)</math> aus. Dafür bietet dieser Algorithmus den Vorteil eines geringen Speicherbedarfes. Da der Algorithmus ein [[In-place]]-Verfahren ist, braucht er keinen zusätzlichen Speicher. Zudem hat Shakersort auf fast sortierten Arrays eine lineare Laufzeitkomplexität (<math>\textstyle\Theta(n)</math>).

== Formaler Algorithmus ==
Der Algorithmus sieht im [[Pseudocode]] folgendermaßen aus. Das erste Element der Liste sortierbarer Elemente <code>A</code> hat hierbei den Index 0:

'''prozedur''' shakerSort( A ''':''' Liste sortierbarer Elemente )
beginn := -1
ende := Länge( A ) - 2
'''wiederhole'''
vertauscht := falsch
beginn := beginn + 1
'''für jedes''' i '''von''' beginn '''bis''' ende '''wiederhole'''
'''falls''' A[ i ] > A[ i + 1 ] '''dann'''
vertausche( A[ i ], A[ i + 1 ] )
vertauscht := wahr
'''ende falls'''
'''ende für'''
'''falls''' vertauscht = falsch '''dann'''
'''brich wiederhole-solange-Schleife ab'''
'''ende falls'''
vertauscht := falsch
ende := ende - 1
'''für jedes''' i '''von''' ende '''bis''' beginn '''wiederhole'''
'''falls''' A[ i ] > A[ i + 1 ] '''dann'''
vertausche( A[ i ], A[ i + 1 ] )
vertauscht := wahr
'''ende falls'''
'''ende für'''
'''solange''' vertauscht
'''prozedur ende'''

== Beispiel ==

Eine Reihe von sechs Zahlen soll aufsteigend sortiert werden. Die fett markierten Zahlenpaare werden verglichen. Wenn die rechte Zahl hierbei kleiner ist als die linke, so werden die Zahlen vertauscht (blau markiert).

'''55 07''' 78 12 42 33 1. Durchlauf
07 '''55 78''' 12 42 33
07 55 '''78 12''' 42 33
07 55 12 '''78 42''' 33
07 55 12 42 '''78 33'''
07 55 12 '''42 33''' 78 2. Durchlauf
07 55 '''12 33''' 42 78
07 '''55 12''' 33 42 78
'''07 12''' 55 33 42 78
07 '''12 55''' 33 42 78 3. Durchlauf
07 12 '''55 33''' 42 78
07 12 33 '''55 42''' 78
07 12 '''33 42''' 55 78 4. Durchlauf
07 '''12 33''' 42 55 78 // Algorithmus terminiert, da im 4. Durchlauf nicht mehr getauscht wurde (Abbruchbedingung)
07 12 33 42 55 78 // Fertig sortiert. Der 5. Durchlauf wird nicht mehr begonnen.

== Weblinks ==
* [http://www.hermann-gruber.com/lehre/sorting/Shaker/Shaker.html Visualisierung von Shakersort als Java-Applet]
* [https://www.sortieralgorithmen.de/shakersort/index.html sortieralgorithmen.de]

[[Kategorie:Sortieralgorithmus]]

Shakersort - Versionsgeschichte

imported>Trustable: linkfix