Gnomesort

Gnomesort ist ein sehr einfacher und stabiler 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 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.

Ein weiterer Ansatz, diesen Sortieralgorithmus zu erklären, ist, den Vergleich zu Bubblesort heranzuziehen. Dabei betrachtet man Gnomesort nur als Variante von Bubblesort, welche bei einem erfolgreichen Tausch von Elementen die Tauschrichtung beziehungsweise die Vergleichsrichtung wechselt, was die Blasen gegebenenfalls schneller aufsteigen lässt. Das Einarbeiten einer Abbruchbedingung, um einen schnelleren Ausstieg bei einem fertig sortierten Array zu gewährleisten, ist jedoch bei den meisten Implementierungen nicht notwendig.

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

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 $\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.

Einzelnachweise

1. ↑ Gnomesort auf der Webseite von Dick Grune