Grundlegend ist Shakersort (auch Cocktailsort genannt) eine Variation von dem Sortieralgorithmus Bubblesort. Somit gehen wir als erstes auf Bubblesort ein:

Bubblesort:
Der Bubblesort-Algorithmus funktioniert, indem er die Liste mehrmals durchgeht, benachbarte Elemente vergleicht und sie gegebenenfalls tauscht, bis die gesamte Liste sortiert ist. Es ist zwar einfach zu verstehen, aber Bubblesort hat eine ineffiziente Laufzeit von \( \theta(n^2) \) (Worst-Case; Liste komplett falschherum), was bedeutet, dass er bei großen Listen sehr langsam sein kann. Dies führt uns zur Frage: Gibt es eine bessere Möglichkeit, Listen zu sortieren? Ja, Shakersort!

Funktionsweise Shakersort:
Die Grundidee hinter Shakersort ist es, Bubblesort zu optimieren, indem er die Liste in zwei Richtungen gleichzeitig durchläuft. Während Bubblesort nur von links nach rechts geht, geht Shakersort abwechselnd von links nach rechts und von rechts nach links.

Um dies nochmal zu verdeutlichen, ist hier eine Visualisierung:

Optimierung:
Die folgende Optimierung kann auch bei Bubblesort vorgenommen werden:
Nach dem ersten Durchlauf wird das größte und kleinste Element nach ganz rechts bzw. links verschoben. Im nächsten Durchlauf wird das nächstgrößere/kleinere Element nach (fast) rechts/links verschoben. Somit können wir diese Elemente in den nächsten Vergleichen überspringen.
Somit kommen auf folgende Worst-Case-Laufzeit: \( \theta(\sum_{i=1}^{n}i) \)

Warum Shakersort?
Shakersort vermeidet unnötige Durchläufe bei Vorsortierten Listen. Ein Beispiel ist die Liste: 1, 6, 3, 4, 5, 2. Shakersort braucht nur einen Durchlauf, da Shakersort vorwärts und rückwärts läuft. Für die gleiche Liste braucht Bubblesort vier Vergleiche.

Implementation des Algorithmus:
Hier ist die JavaScript-Implementierung des Sortieralgorithmus Shakersort:
function shakersort(a) { //a ist die unsortierte Liste let swapped = true; let start = 0; let end = a.length - 1; while (swapped == true) { swapped = false; //schleife von vorne nach hinten wie bei der bubblesort for (let i = start; i < end; ++i) { if (a[i] > a[i + 1]) { let temp = a[i]; a[i] = a[i + 1]; a[i + 1] = temp; swapped = true; } } //wenn sich nichts bewegt hat, ist die Liste sortiert. if (swapped == false) break; //Andernfalls setzen Sie das Swapped-Flag zurück swapped = false; //verschiebendes Endpunktes um eins nach hinten, da sich das Element am Ende an seiner endgültigen Position befindet end = end - 1; //von hinten nach vorne, wobei der gleiche Vergleich wie in der vorherigen Phase durchgeführt wird for (let i = end - 1; i >= start; i--) { if (a[i] > a[i + 1]) { let temp = a[i]; a[i] = a[i + 1]; a[i + 1] = temp; swapped = true; } } //erhöhen des Startpunktes, da sich das Element am Anfang an seiner endgültigen Position befindet start = start + 1; } }

Fazit:
Shakersort ist eine Variation des Sortieralgorithmus Bubblesort und vermeidet in bestimmten Listen unnötige Durchläufe und hat trotzdem die gleiche Anzahl an Vergleichen bei komplett unsortierten Listen.