Gnomesort

Grundidee und Ablauf

Gnomesort ist ein sehr einfacher, stabiler Sortieralgorithmus. Stabil bedeutet, dass Elemente mit gleichem Sortierwert ihre ursprüngliche Reihenfolge behalten. Er sortiert eine Folge von n Elementen aufsteigend, indem er jeweils zwei benachbarte Elemente vergleicht.

Anschaulich steht ein Gartenzwerg links vor einer Reihe unterschiedlich großer Blumentöpfe. Sind die zwei Töpfe vor ihm richtig angeordnet, geht er einen Schritt nach rechts. Sind sie falsch angeordnet, vertauscht er sie und geht einen Schritt nach links. Am linken Rand kann er nicht weiter zurückgehen und geht dann nach rechts. Der Vorgang wiederholt sich, bis er den ganz rechten Topf erreicht; rechts davon gibt es kein weiteres Element zum Vergleichen.

Vergleich mit Insertionsort und Bubblesort

Gnomesort führt dieselben Vertauschungsoperationen wie Insertionsort aus, wiederholt jedoch manche Vergleiche. Insertionsort speichert den letzten oberen Listenindex – meist durch eine For-Schleife – und kann nach dem erfolgreichen Runterbubblen eines Elements direkt dort fortfahren. Gnomesort muss dagegen durch weitere, eigentlich unnötige Vergleiche zu dieser Stelle zurückkehren.

Außerdem verschiebt Insertionsort Elemente, statt sie jeweils zu vertauschen; Verschiebungen sind kostengünstiger. Weil Gnomesort beide Optimierungen nicht verwendet, ist er langsamer, aber besonders leicht zu programmieren. Seine Stärke liegt daher in Situationen, in denen die Laufzeit nicht wichtig ist.

Gegenüber Bubblesort steigen die „Blasen“ oft nur langsam auf, fallen jedoch immer n · Position im Array Mal schneller ab. Im Best- und Worst-Case ist Gnomesort genauso schnell wie Bubblesort, in anderen Fällen schneller.

Laufzeit und Speicherbedarf

Im Worst Case benötigt Gnomesort quadratische Laufzeit: Θ(n²). Das ist im Vergleich zu vielen anderen Sortieralgorithmen schlecht. Im Best Case beträgt die Laufzeit Θ(n).

Gnomesort ist ein In-place-Verfahren: Es sortiert direkt in der vorhandenen Datenstruktur und benötigt nur vernachlässigbaren konstanten zusätzlichen Speicher.