Wikipedia · einfach zusammengefasst · Stand
Shakersort
Der Begriff Shakersort bezeichnet einen stabilen Sortieralgorithmus, der eine Menge von linear angeordneten Elementen (z. B. Zahlen) der Größe nach sortiert …
Inhalt4 Abschnitte
Einordnung und Grundidee
Shakersort ist ein stabiler Sortieralgorithmus für linear angeordnete Elemente, zum Beispiel Zahlen. Stabil bedeutet, dass Elemente mit gleichem Wert ihre ursprüngliche Reihenfolge beibehalten. Weitere Namen sind Cocktailsort, Ripplesort, Shearsort und BiDiBubbleSort, also bidirektionales Bubblesort.
Das Verfahren durchläuft das zu sortierende Feld abwechselnd vorwärts und rückwärts. Dabei vergleicht es jeweils zwei benachbarte Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge stehen. Durch diese Bidirektionalität gelangen große Elemente schneller an das obere beziehungsweise rechte Ende und kleine Elemente schneller an das untere beziehungsweise linke Ende.
Ablauf des Algorithmus
Für eine Liste A, deren erstes Element den Index 0 hat, werden zunächst die Grenzen beginn := −1 und ende := Länge(A) − 2 gesetzt.
In jedem Schleifendurchgang wird beginn um 1 erhöht. Anschließend läuft der Algorithmus von beginn bis ende vorwärts. Für jeden Index i vergleicht er A[i] mit A[i + 1]. Falls A[i] > A[i + 1] gilt, werden beide Elemente vertauscht und die Variable vertauscht auf wahr gesetzt.
Gab es beim Vorwärtslauf keinen Tausch, wird die Schleife abgebrochen, weil die Liste bereits sortiert ist. Andernfalls wird vertauscht wieder auf falsch gesetzt und ende um 1 verringert. Danach folgt ein Rückwärtslauf von ende bis beginn, bei dem erneut benachbarte Elemente verglichen und bei Bedarf vertauscht werden. Die Vorwärts- und Rückwärtsläufe werden wiederholt, solange dabei noch ein Tausch stattfindet.
Laufzeit und Speicherbedarf
Im schlechtesten Fall besitzt Shakersort eine quadratische Laufzeit von Θ(n²). In der einfachen Version entspricht dies zugleich der normalen Laufzeit. Damit ist das Verfahren im Vergleich zu vielen anderen Sortieralgorithmen langsam.
Bei fast sortierten Feldern kann Shakersort dagegen eine lineare Laufzeit von Θ(n) erreichen. Außerdem benötigt der Algorithmus nur wenig Speicher: Er arbeitet als In-place-Verfahren direkt im vorhandenen Feld und braucht daher keinen zusätzlichen Speicher.
Typischer Sortierdurchlauf
Die Zahlenfolge 55 07 78 12 42 33 soll aufsteigend sortiert werden. Im ersten Vorwärtslauf wandert 78 durch mehrere Vertauschungen bis an das rechte Ende; die Folge lautet danach 07 55 12 42 33 78. Beim anschließenden Lauf in die Gegenrichtung werden kleinere Werte weiter nach links bewegt.
Nach weiteren Durchläufen entstehen unter anderem 07 12 55 33 42 78 und anschließend 07 12 33 42 55 78. Im 4. Durchlauf findet keine Vertauschung mehr statt. Deshalb terminiert der Algorithmus mit der vollständig sortierten Folge 07 12 33 42 55 78; ein 5. Durchlauf wird nicht mehr begonnen.
