imported>Serols: Änderungen von 89.1.94.10 (Diskussion) auf die letzte Version von Serols zurückgesetzt

2023-04-27T11:20:51Z

Änderungen von 89.1.94.10 (Diskussion) auf die letzte Version von Serols zurückgesetzt

Neue Seite

[[Datei:Sorting gnomesort anim.gif|gerahmt|rechts|Animation von Insertionsort bzw. von Gnomesort ohne Visualisierung der Vergleichsoperationen, siehe [[#Vergleich|Abschnitt Vergleich]].]]
'''Gnomesort''' ist ein sehr einfacher und [[Stabilität (Sortierverfahren)|stabiler]] [[Sortierverfahren|Sortieralgorithmus]].

== Prinzip ==

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 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.<ref>[https://dickgrune.com/Programs/gnomesort.html Gnomesort] auf der Webseite von Dick Grune</ref>

== Vergleich ==
* 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 [[Bubblesort#Prinzip|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 ==
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 <math>\textstyle\Theta(n^2)</math> aus. Im Best-Case hat dieser Algorithmus eine Laufzeit von <math>\textstyle\Theta(n)</math>. Da der Algorithmus ein [[In-place]]-Verfahren ist, braucht er vernachlässigbaren konstanten zusätzlichen Speicher.

== Literatur ==
* {{Literatur| Autor=Hamid Sarbazi-Azad | Titel=Stupid Sort: A new sorting algorithm | Sammelwerk=Department of Computing Science Newsletter, University of Glasgow | Band= 599 | Nummer=4 | Datum=2000-10-02 }}

== Weblinks ==
* [https://xlinux.nist.gov/dads/HTML/gnomeSort.html NIST-Seite zu Gnomesort]
* [https://dickgrune.com/Programs/gnomesort.html Gnomesort-Seite von Dick Grune]

== Einzelnachweise ==
<references />

[[Kategorie:Sortieralgorithmus]]

Gnomesort - Versionsgeschichte

imported>Serols: Änderungen von 89.1.94.10 (Diskussion) auf die letzte Version von Serols zurückgesetzt