Gnome sort

Gnome sort is a sort algorithm which is similar to insertion sort except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. The name comes from the supposed behavior of the Dutch garden gnome in sorting a line of flowerpots. It is conceptually simple, requiring no nested loops. The running time is O(n²), and in practice the algorithm has been reported to run slightly slower than bubble sort, although this depends on the details of the architecture and the implementation.

Description

Here is pseudocode for the sort:

 function gnomeSort(a[1..size]) {
    i := 2
    while i ≤ size
        if i = 1 or a[i-1] ≤ a[i]
            i := i + 1
        else
            swap a[i-1] and a[i]
            i := i - 1
 }

Effectively, the algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. If this place were searched for naively, the result would be the O(n³) stupid sort. Instead, it takes advantage of the fact that performing a swap can only introduce a new out-of-order adjacent pair right before the two swapped elements, and so checks this position immediately after performing such a swap.

Implementations

C++

 int gnomeSort(int array[], int size)
 {
   int i = 1;
   int swapNum;
   while (i<size)
   {
     if (i==0 || array[i-1]<= array[i])
       i++; //Increment i
     else
     {
       //SWAP NUMBERS
       swapNum = array[i-1];
       array[i-1] = array[i];
       array[i] = swapNum;
       i--; //Decrement i
     };
   };
 };

--OptiKal Mouse 02:08, 10 Dec 2004 (UTC)

Perl

sub gnome_sort(@)
{
  my @a = @_;
  my $i=0;
  while ($i < @a) {
    if ($i==0 or $a[$i-1] <= $a[$i]) {
      $i++;
    } else {
      ($a[$i-1],$a[$i]) = ($a[$i],$a[$i-1]);
      $i--;
    }
  }
  return @a;
}

Python

def gnome_sort(L):
    L = L[:]
    i = 0
    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
    return L

External link

• Gnome sort.