Heim

Gnomesort

Gnomesort ist ein sehr einfacher und stabiler Sortieralgorithmus.

Inhaltsverzeichnis

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.

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.

Implementierung

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--;
         }
     }
 }

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;
}


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;
 }

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.

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;

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"

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));

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;

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

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

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

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