Gnomesort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Animation von Insertionsort bzw. von Gnomesort ohne Visualisierung der Vergleichsoperationen, siehe Abschnitt Vergleich.

Gnomesort ist ein sehr einfacher und stabiler Sortieralgorithmus.

Prinzip[Bearbeiten]

Man stelle sich einen Gartenzwerg (garden gnome) vor, welcher vor n Blumentöpfen steht, die unterschiedliche Größen haben dürfen. Die Blumentöpfe sind in einer von links nach rechts verlaufenden Reihe aufgestellt. Ganz links steht der Gartenzwerg und möchte die Blumentöpfe von links nach rechts der Größe nach aufsteigend sortieren.

Dazu vergleicht er die beiden Blumentöpfe, vor denen er grade steht. Stellt er fest, dass sie in der richtigen Reihenfolge sind, so macht er einen Schritt nach rechts. Stellt er hingegen fest, dass die Reihenfolge nicht stimmt, so vertauscht er die beiden Blumentöpfe und macht einen Schritt nach links. Falls er nicht weiter nach links gehen kann (wenn beispielsweise der erste Vergleich zum Ergebnis führte, dass sich der erste und zweite Blumentopf in der falschen Reihenfolge befanden), macht er einen Schritt nach rechts. Dies wiederholt er ständig. Fertig ist er, wenn er am ganz rechts stehenden Blumentopf ankommt. Da sich rechts daneben kein weiterer Blumentopf mehr befindet, kann kein Vergleich mehr stattfinden.

Gnomesort wurde im Jahr 2000 zuerst als „Stupid Sort“ beschrieben von Hamid Sarbazi-Azad und später von Dick Grune als Gnomesort bezeichnet.[1]

Vergleich[Bearbeiten]

Gnomesort führt die selben Vertauschungsoperationen wie Insertionsort durch, vergleicht aber einige Elemente mehrmals.
Genauer gesagt der Unterschied ist, daß Insertionsort dahingehend optimiert ist, daß es den letzten oberen Listenindex speichert (meist versteckt in Form einer For-Schleife) und nach dem erfolgreichen Runterbubblen somit direkt dort fortsetzen kann; Gnomesort hingegen führt eine Reihe erneuter (eigentlich unnötiger) Vergleiche durch um zum letzten oberen Index zurückzukommen.
Zudem führt Insertionsort statt Vertauschungen eigentlich nur kostengünstigere Verschiebungen aus.
Diese beiden fehlenden Optimierungen machen Gnomesort aber zu einem der am einfachsten zu programmierenden Sortieralgorithmen und sind damit gerade seine besondere Stärke, wenn es nicht auf Laufzeit ankommt.

Im Vergleich zu Bubblesort steigen die Blasen nur sehr langsam auf, aber dafür zusätzlich ab.
Dadurch ist Gnomesort oft schneller als Bubblesort, aber zum Beispiel im Worst-Case einer rückwärts sortierten Liste hat Bubblesort weniger Vergleiche als Gnomesort.

Laufzeitanalyse[Bearbeiten]

Der Algorithmus besitzt eine quadratische und daher im Vergleich zu vielen anderen Sortieralgorithmen schlechte Worst-Case-Laufzeit. In der Informatik drückt man dies mittels Landau-Symbol durch \textstyle\mathcal{O}(n^2) aus. Im Best-Case hat dieser Algorithmus eine Laufzeit von \textstyle\mathcal{O}(n). Da der Algorithmus ein In-place-Verfahren ist, braucht er vernachlässigbaren konstanten zusätzlichen Speicher.

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Gnomesort auf der Webseite von Dick Grune

Literatur[Bearbeiten]

  •  Hamid Sarbazi-Azad: Stupid Sort: A new sorting algorithm. In: Department of Computing Science Newsletter, University of Glasgow. Nr. 4, 2. Oktober 2000.

Weblinks[Bearbeiten]