GnomeSort habe ich nicht erfunden. Das Verfahren ist recht bildhaft auf Wikipedia beschrieben, daher sei es hier zitiert:
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. Dies wiederholt er ständig. Fertig ist er, wenn er am ganz rechts stehenden Blumentopf ankommt und feststellt, dass dieser in der richtigen Reihenfolge steht.
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 Kontrollbedingung, um einen schnelleren Ausstieg bei einem fertig sortierten Array zu gewährleisten, ist jedoch bei den meisten Implementierungen nicht notwendig. Quelle: Wikipedia: GnomeSort
Auch wenn auf Wikipedia GnomeSort mit BubbleSort verglichen wird, sieht das Verfahren in der Visualisierung eher aus wie InsertionSort (um nicht zu sagen: fast ganz genauso!). Das liegt daran, dass bei BubbleSort mit jedem äußeren Schleifendurchlauf mindestens ein Element seine endgültige Position findet, während bei GnomeSort genau wie bei InsertionSort die meisten Elemente erst kurz vor Schluss auf ihren endgültigen Platz gelangen.
Während InsertionSort aber mit zwei Schleifen arbeitet (wobei die Wiederholung der äußeren durch die Anzahl der Elemente vorgegeben ist), kommt GnomeSort mit einer einzigen aus. Darin wird aber immer wieder mal vor und zurück gesprungen, so dass die Laufzeit ziemlich unberechenbar ist.
Sub GnomeSort(aDaten())
Dim i As Long, varTemp, j As Long, n As Long
n = UBound(aDaten)
i = 1
Do While i < UBound(aDaten)
If aDaten(i) > aDaten(i + 1) Then
varTemp = aDaten(i)
aDaten(i) = aDaten(i + 1)
aDaten(i + 1) = varTemp
If i > 1 Then
i = i - 1
Else
i = i + 1
End If
Else
i = i + 1
End If
j = j + 1
Loop
End Sub
Code eingefügt mit Syntaxhighlighter 3.0
|
