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 and sometimes faster, 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 a[i-1] ≤ a[i]
        i := i + 1
    else
        swap a[i-1] and a[i]
        i := i - 1
        if i = 1
          i := 2
 }

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 O(n³). 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#

void GnomeSort( int[] array )
{
  for ( int i = 1, temp_value; i < array.Length; )
  {
    if ( array[i-1] <= array[i] )
      i += 1;
    else
    {
      temp_value = array[i-1];
      array[i-1] = array[i];
      array[i] = temp_value;
      i -= 1;
      if ( i == 0 )
        i = 1;
    }
  }
}

C++

 #include <algorithm> // for std::swap
 void gnomeSort( int* array, int size )
 {
   for ( int i = 1; i < size; ) {
     if ( array[i-1] <= array[i] ) {
       ++i;
     }
     else {
       std::swap( array[i-1], array[i] );
       --i;
       if ( i == 0 ) {
         i = 1;
       }
     }
   }
 }

Perl

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

Python

def gnome_sort(L):
  L = L[:]
  i = 1
  while i < len(L):
    if L[i-1] <= L[i]:
      i += 1
    else:
      L[i], L[i-1] = L[i-1], L[i]
      i -= 1
      if i == 0:
        i = 1
  return L

FORTRAN 77

 SUBROUTINE gnome_sort(A, LEN)
 INTEGER A, LEN, I, TEMP
 DIMENSION A(LEN)
 I = 2
 WHILE (I .LE. LEN) DO
   IF ((I .EQ. 1) .OR. (A(I-1) .LE. A(I))) THEN
     I = I + 1
   ELSE
     TEMP = A(I)
     A(I) = A(I-1)
     A(I-1) = TEMP
     I = I - 1
     IF (I .EQ. 1) THEN
       I = 2
     END IF
   END IF
 END WHILE
 END

Java

 public class GnomeSort {
    static void gnomeSort( int[] theArray ) {
       for ( int index = 1; index < theArray.length; ) {
          if ( theArray[index - 1] <= theArray[index] ) {
             ++index;
          } else {
             int tempVal = theArray[index];
             theArray[index] = theArray[index - 1];
             theArray[index - 1] = tempVal;
             --index;
             if ( index == 0 ) {
                index = 1;
             }		
          }
       }
    }
 }

C

    void gnome_sort(int *array, int size) {
       int i;
       int tmp;
       for (i = 1; i < size; ) {
          if (array[i - 1] <= array[i] ) {
             ++i;
          } else {
             tmp = array[i];
             array[i] = array[i - 1];
             array[i - 1] = tmp;
             --i;
             if ( i == 0 ) {
                i = 1;
             }		
          }
       }
    }

External link

• Gnome sort