Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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 oder BiDiBubbleSort (bidirektionales Bubblesort).

Inhaltsverzeichnis 1 Prinzip 2 Komplexität 3 Implementierungen 3.1 Ruby 4 Siehe auch 5 Weblinks

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 schnellerem 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 Parser-Fehler (Unbekannte Funktion \textstyle): \textstyle\mathcal{O}(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.

Implementierungen

Ruby

def bidibubblesort!(arr)
  t = arr.size - 1
  for i in 1..arr.size
    for j in (i-1)..arr.size-1-i
      if (arr[t-j] < arr[t-(j+1)])
        arr[t-j], arr[t-(j+1)] = arr[t-(j+1)], arr[t-j]
      end
      if (arr[j] > arr[j+1])
        arr[j], arr[j+1] = arr[j+1], arr[j]
      end
    end
  end
end

Siehe auch

• Bubblesort
• Liste von Sortieralgorithmen

Weblinks

• Visualisierung von Shakersort als Java-Applet
• Erklärung des Shakersort-Algorithmus
• http://www.sortieralgorithmen.de/shakersort/index.html

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Shakersort, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.