Gnomesort

Gnomesort ist ein sehr einfacher Sortieralgorithmus, der nach folgendem Prinzip arbeitet:

Gegeben: Eine Liste A der Länge n.

• Setze eine Variable i auf 0
• Wiederhole die folgenden Schritte, bis die Liste fertig sortiert ist:
  • Betrachte A[i] und A[i+1]
  • Wenn A[i] ≤ A[i+1], ...
    • ... erhöhe i um 1.
    • Falls nun i = n-1 ist, ist die Liste fertig sortiert.
  • Wenn A[i] > A[i+1], ...
    • ... vertausche die beiden.
    • Falls i > 0, verringere i um 1

Laufzeit

Gnomesort ist am schnellsten, wenn die Liste bereits der Größe nach sortiert ist, weil dann jede Zahl nur einmal betrachtet und nicht vertauscht werden muss.

Gnomesort ist am langsamsten, wenn die Liste umgekehrt sortiert ist, weil jede Zahl schrittweise an ihre korrekte Position ertauscht werden muss und dann ebenso schrittweise wieder zum Ende des sortierten Bereichs gehüpft werden muss.

Die Laufzeit von Gnomesort bewegt sich darum im besten Fall in der Größenordnung ${𝒪}(n)$ und im schlechtesten Fall in der Größenordnung ${𝒪}(n^2)$.

Weblinks

• Sortieralgorithmen auf VisuAlgo.net 🇬🇧 🇨🇳 🇮🇩

Sortieralgorithmen

Bubblesort | Selectionsort | Insertionsort | Quicksort | Mergesort | Gnomesort