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. Wobei man Gnomesort nur als Variante von Bubblesort betrachtet, 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] Implementierung
[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:=0;
while i<=length(feld)-1 do
begin
if i<0 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] 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] 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] C++
#include <iostream>
using namespace std;
void swap(int &x,int &y);
void gnomesort(int ar[],int n);
int main(void)
{
int x[7]={7,4,5,7,1,2,1};
gnomesort(x,7);
return 0;
}
void gnomesort(int ar[],int n)
{
int i=0;
while(i<n)
{
cout << endl;
for(int k=0;k<n;k++)
{
if(i==k)
cout << "x";
else
cout << " ";
cout << ar[k];
}
if (i==0 || ar[i-1]<=ar[i])
i++;
else
{
swap(ar[i-1],ar[i]);
i--;
}
}
}
void swap(int &x,int &y)
{
int temp=x;
x=y;
y=temp;
}
[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] 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] 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] Beispiel
Schreibtischtest:
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
