Der Shakersort ist eine abgewandelte (verbesserte) Form des Bubblesort. Er gehört zur Gruppe der elementaren Sortieralgorithmen.
Der Shakersort durchlauft ein Array vollständig von links nach rechts und vergleicht dabei die Nachbarelemente. Falls nötig, tauscht er diese aus. Danach durchläuft er das Array erneut, diesmal von rechts nach links, und vergleicht wiederum die Nachbarelemente bzw. tauscht sie aus. Dieser Schritt wird immer wieder wiederholt, bis das Array fertig sortiert ist.
Der Shakersort ist vor allem dann nützlich, wenn ein großer Teil des Feldes sortiert vorliegt. Jedoch ist die Verbesserung gegenüber dem Bubbelsort nur gering, da nur Vergleiche vermieden werden, und meist Vertauschungen aufwendiger sind. Somit ergibt sich eine ungefähre Komplexität von O(n²).
Beim Shakersort handelt es sich wie beim Bubblesort um einen stabilen Sortieralgorithmus.
Stabile Sortieralgorithmen lassen die Reihenfolge von gleichen Elementen unverändert. Dies spielt dann eine Rolle, wenn nicht alle Attribute der Elemente in den Vergleich eingehen. Wenn wir etwa die Folge (27,1), (3,2), (56,1), (4,2) (3,1) nach der zweiten Komponente der Zahlenpaare sortieren und anschließend nach der ersten Komponente, dann erwarten wir, dass (3,1) vor (3,2) liegt und der Algorithmus die Reihenfolge der beiden Zahlenpaare nicht wieder ändert. Diese Eigenschaft ist nur dann garantiert, wenn die zweite Sortierung mit einem stabilen Sortieralgorithmus erfolgt. Etwas praktischer lässt sich diese Eigenschaft an einem E-Mail-Programm demonstrieren. Sortieren wir unsere Nachrichten zuerst nach dem Datum und anschließend nach dem Absender, so sollen die Nachrichten von demselben Absender immer noch nach dem Datum sortiert bleiben.
void shakersort(int array[ARRAY_LENGTH]) { int ende = ARRAY_LENGTH; int start = -1; int temp = 0; while (start < ende) { start++; ende--; int swapped = 0; for (int i = start; i <= ende; i++) { if (array[i]>array[i+1]) { temp = array[i]; array[i] = array[i+1]; array[i+1] = temp; swapped = 1; } } if (!swapped) break; else swapped = 0; for (int i = ende; i-1 >= start; i--) { if (array[i] > array[i+1]) { temp = array[i]; array[i] = array[i+1]; array[i+1] = temp; swapped = 1; } } if (!swapped) break; } }