Gnomesort
Gnomesort ist ein sehr einfacher und stabiler Sortieralgorithmus.
Prinzip
BearbeitenMan 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 gerade 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 dieselben Vertauschungsoperationen wie Insertionsort durch, vergleicht aber einige Elemente mehrmals.
- Genauer gesagt ist der Unterschied, dass Insertionsort dahingehend optimiert ist, dass 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 oft nur langsam auf, dafür aber immer n * Position im Array Mal schneller ab.
- Im Best- und Worst-Case ist Gnomesort immer genauso schnell wie Bubblesort und ansonsten immer schneller.
Laufzeitanalyse
BearbeitenDer 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 aus. Im Best-Case hat dieser Algorithmus eine Laufzeit von . Da der Algorithmus ein In-place-Verfahren ist, braucht er vernachlässigbaren konstanten zusätzlichen Speicher.
Literatur
Bearbeiten- Hamid Sarbazi-Azad: Stupid Sort: A new sorting algorithm. In: Department of Computing Science Newsletter, University of Glasgow. Band 599, Nr. 4, 2. Oktober 2000.