Sortieralgorithmen/ Gnomesort

Gnomesort ist ein einfacher Sortieralgorithmus der leicht zu erklären ist. Die Bezeichnung Gnomesort kommt aus dem Vergleich mit einem Gnom der Gartentöpfe nach Größe sortiert. (6)

Vorher wurde im Jahre 2000 Gnomesort als Stupidsort bezeichnet.

Bei Gnomesort werden die ersten beiden Zahlen verglichen. Die kleinere Zahl wird an den Anfang gestellt, also an die erste Stelle. Hätten wir nun zum Beispiel eine Zahlenreihe 4,3,6,1 dann würden jetzt die Vier mit der Drei vertauscht werden also 3,4,6,1. Im nächsten Schritt wird die nun zweite Zahl mit der dritten verglichen in unserem Beispiel wären das die Zahlen 4 und 6. Die Zahlenreihenfolge stimmt überein. Demzufolge werden die Zahlen stehen gelassen. Als nächstes wird die 6 mit der 1 verglichen. Da es nicht passt, werden die beiden Zahlen vertauscht. Nun ist die Zahlenreihe 3,4,1,6. Da links von der Eins noch eine Zahl steht, wird die Eins nun mit dieser verglichen und vertauscht, solange bis die Eins entweder größer, als die links von ihr stehende Zahl ist, oder links von ihr keine Zahl mehr steht. Ist dieser Schritt abgeschlossen, dann ist die Zahlenfolge 1,3,4,6. Nun wird die Zahl, die rechts der ersten Position, der Eins, wo nun also die Sechs steht genommen. Da dort aber keine Zahl mehr steht, ist die Zahlenreihe fertig sortiert. Angenommen es würde dort aber noch eine Zahl stehen, würde diese auch an die richtige Stelle sortiert werden.

Ich habe mir ein Beispiel ausgedacht um Gnomesort bildhaft darzustellen. Ein Sportlehrer hat eine neue Klasse vor sich stehen. Alle Schüler der Klasse stehen irgendwo in einer Reihe. Der Sportlehrer will sie nun der Größe nach ordnen, also ruft er die beiden Schüler, die am Anfang der Reihe stehen auf, Plätze zu tauschen, da der am zweiten Platz stehende Schüler mit seiner Größe von 1.10 m kleiner, als der erste Schüler mit 1.20 m war. Nun geht der Lehrer ein Schritt nach rechts und schaut sich den nun zweiten Schüler und den dritten Schüler mit 1.30 m an.

Diese beiden stehen in der richtigen Reihenfolge sagt er, geht nochmals ein Schritt nach rechts und vergleicht den dritten mit dem vierten Schüler. Der vierte ist wie der dritte auch 1.30 m groß. Deswegen lässt der Sportlehrer auch diese beiden so stehen, wie sie sind und geht auch hier wieder einen Schritt nach rechts. Hier vergleicht er nun den vierten mit dem fünften Schüler. Da dieser nur 1.05 m groß ist, vertauscht er ihn mit dem vierten und geht nun einen Schritt nach links, um den jetzt vierten mit dem dritten zu vergleichen. Da der dritte Schüler auch, wie der jetzt fünfte Schüler 1.30 m groß ist, muss er die beiden jetzt auch vertauschen, so dass der Schüler, der 1.05 m groß ist nun an der dritten Stelle der Reihe steht.

Auch jetzt geht der Lehrer wieder einen Schritt nach links, damit er den an zweiter Stelle stehenden mit dem an dritter Stelle stehenden Schüler vergleichen kann. Der zweite Schüler ist 1.20 m groß, während der dritte gerade mal 1.05 m groß ist. Also tauschen auch diese beiden. Jetzt geht der Lehrer wieder ein Schritt nach links, wo er den zweiten mit dem ersten Schüler vergleicht. Der erste ist 1.10 m groß, der jetzige zweite aber nur 1.05 m Also müssen auch die beiden wieder tauschen. Da links des ersten Schülers keiner mehr steht, geht er an die Stelle, wo der nun erste Schüler stand, also zu der fünften Position. Da die Hälfte der Klasse krank ist, steht rechts des fünften Schülers nur noch eine Person, welche aber nun auch einsortiert werden soll. Der Lehrer vergleicht nun den fünften mit dem sechsten Schüler, dieser ist mit 1.35 m größer als der fünfte Schüler, deshalb bleiben beide stehen. Jetzt sind alle Schüler ordentlich der Größe nach in einer Reihe sortiert.

Gnomesort benötigt keinen weiteren Speicherplatz und ist deshalb ein in-place Algorithmus.