Gnomesort
aus Wikipedia, der freien Enzyklopädie
Gnomesort ist ein sehr einfacher und stabiler Sortieralgorithmus.
Inhaltsverzeichnis |
[Bearbeiten] 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. 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.
Gnomesort [1] wurde zuerst beschrieben von Dick Grune [2], Vrije Universiteit, Amsterdam.
[Bearbeiten] 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 
aus. Im Best-Case hat dieser Algorithmus eine Laufzeit von 
. Da der Algorithmus ein In-place-Verfahren ist, braucht er vernachlässigbaren konstanten zusätzlichen Speicher.
[Bearbeiten] Implementierung
[Bearbeiten] C
/** * size: Anzahl der Elemente in heap * heap: Eindimensionales Array, bestehend aus Integern */ void gnomesort(int size, int *heap) { int i = 0, temp; while (i < size) { if (i == 0 || heap[i - 1] <= heap[i]) { i++; } else { temp = heap[i]; heap[i] = heap[i - 1]; heap[i - 1] = temp; i--; } } }
[Bearbeiten] C++
#include <iostream> using namespace std; void swap(int &x,int &y); void gnomesort(int* arr, int size); int main(void) { int x[7]={7,4,5,7,1,2,1}; //Array erstellen gnomesort(x,7); //Sortieren for(int i=0; i<7; i++) cout<<x[i]<<endl; //Alle Werte ausgeben return 0; } void gnomesort(int* arr, int size) { for(int i=1; i<size;) { if(arr[i-1] < arr[i]) { swap(arr[i-1], arr[i]); if(i > 1) i--; } else i++; } } void swap(int &x,int &y) { int temp=x; x=y; y=temp; }
[Bearbeiten] Java
public int[] gnomeSort(int[] a) { for (int i = 0; i < a.length;) { if (i == 0 || a[i-1] <= a[i]) { i++; } else { swap(a, i, i - 1); i--; } } return a; }
[Bearbeiten] Pascal
PROGRAM gnomesort; CONST nmax=10000; VAR i,n,h:integer; a:ARRAY [1..nmax] OF integer; BEGIN writeln('Wie viele Elemente');readln(n); FOR i:=1 TO n DO BEGIN writeln(i,'. Element');READLN(a[i]); END; i:=1; WHILE i<n DO BEGIN IF a[i]>a[i+1] THEN BEGIN h:=a[i]; a[i]:=a[i+1]; a[i+1]:=h; i:=i-1; END ELSE i:=i+1; IF i=0 THEN i:=1; END; writeln; FOR i:=1 TO n DO writeln(i,' ',a[i]); END.
[Bearbeiten] Pascal und Delphi
procedure GnomeSort(var Feld: array of Integer); var i, Temp :Integer; begin i := Low(Feld); while i <= High(Feld) do begin if i < Low(Feld) then Inc(i); if Feld[i] > Feld[i + 1] then begin Temp := Feld[i]; Feld[i] := Feld[i + 1]; Feld[i + 1] := Temp; Dec(i); end else Inc(i); end; end;
[Bearbeiten] Perl
sub gnome{ my $l, $j; for($j=0;$j<$#_;$j++){ if(@_[$j]>@_[$j+1]){ (@_[$j],@_[$j+1])=(@_[$j+1],@_[$j]); for($l=$j;$l>0;$l--){ if(@_[$l]<@_[$l-1]){ (@_[$l-1],@_[$l])=(@_[$l],@_[$l-1]) }else{last} } } }return@_ } @array=gnome(@array); print"@array\n"
[Bearbeiten] PHP
function gnomeSort($a) { $i=0; while($i<count($a)) { if($i==0 || $a[$i-1]<=$a[$i]) { $i++; } else { $tmp = $a[$i]; $a[$i] = $a[$i-1]; $a[$i-1] = $tmp; $i--; } } return $a; } $a=Array(1,4,3,2); print_r(gnomeSort($a));
[Bearbeiten] PL/SQL
TYPE t_int_arr IS TABLE OF INTEGER; PROCEDURE gnomesort(feld IN OUT NOCOPY t_int_arr) IS temp VARCHAR2(64); i PLS_INTEGER; BEGIN i := 1; LOOP EXIT WHEN i > feld.COUNT - 1; IF i < 0 THEN i := i + 1; END IF; IF feld(i) > feld(i + 1) THEN temp := feld(i); feld(i) := feld(i + 1); feld(i + 1) := temp; i := i - 1; ELSE i := i + 1; END IF; END LOOP; END;
[Bearbeiten] Python
def gnome_sort(L): i = 1 while i < len(L): if i == 0 or L[i-1] <= L[i]: i += 1 else: L[i], L[i-1] = L[i-1], L[i] i -= 1
[Bearbeiten] Ruby
def gnomesort(list) left = 0 loop do right = left + 1 return list if right >= list.size if list[left] <= list[right] left += 1 else list[left], list[right] = list[right], list[left] left -= 1 left = 0 if left < 0 end end end
[Bearbeiten] Visual Basic
Sub GnomeSort() Dim I, Temp As Integer Do While I < UBound(Feld) - 1 If Feld(I) > Feld(I + 1) Then Temp = Feld(I) Feld(I) = Feld(I + 1) Feld(I + 1) = Temp If I > 0 Then I = I - 1 Else I = I + 1 End If Else I = I + 1 End If Loop End Sub
[Bearbeiten] Beispiel
i a[1] a[2] a[3] a[4] a[5] a[6] a[7] h a[i] a[i+1]
0 7 4 1 8 0 3 5
1 7 4 7
1 4 7 1 8 0 3 5
1 4 7 1 8 0 3 5
2 7 1 7
4 1 7 8 0 3 5
1 4 1 4
1 4 7 8 0 3 5
1 1 4 7 8 0 3 5
2 1 4 7 8 0 3 5
3 1 4 7 8 0 3 5
4 8 0 8
1 4 7 0 8 3 5
3 7 0 7
1 4 0 7 8 3 5
2 4 0 4
1 0 4 7 8 3 5
1 1 0 1
0 1 4 7 8 3 5
1 0 1 4 7 8 3 5
2 0 1 4 7 8 3 5
3 0 1 4 7 8 3 5
4 0 1 4 7 8 3 5
5 8 3 8
0 1 4 7 3 8 5
4 7 3 7
0 1 4 3 7 8 5
3 4 3 4
0 1 3 4 7 8 5
2 0 1 3 4 7 8 5
3 0 1 3 4 7 8 5
4 0 1 3 4 7 8 5
5 0 1 3 4 7 8 5
6 8 5 8
0 1 3 4 7 5 8
5 7 5 7
0 1 3 4 5 7 8
4 0 1 3 4 5 7 8
5 0 1 3 4 5 7 8
6 0 1 3 4 5 7 8
