Shakersort
# Shakersort

Der Begriff Shakersort bezeichnet einen stabilen 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

Das zu sortierende Feld wird abwechselnd nach oben und nach unten durchlaufen. Dabei werden jeweils zwei benachbarte Elemente verglichen und gegebenenfalls vertauscht.

Durch diese Bidirektionalitä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 $\textstyle \Theta (n^{2})$ 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 ($\textstyle \Theta (n)$).

## Formaler Algorithmus

Der Algorithmus sieht im Pseudocode folgendermaßen aus. Das erste Element der Liste sortierbarer Elemente A hat hierbei den Index 0:

## 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).

