Gnome sort

Gnome sort is a sorting 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 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;
             }		
          }
       }
    }

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

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

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

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

PHP

<?php
function gnome_sort($list)
{
    for($i = 1; $i < count($list);)
    {
        if ($list["$i"-1] <= $list["$i"]) {$i++;}
        else
        {
        /* Use bitwise XORing to swap the two elements */
            $list["$i"]   ^= $list["$i"-1];
            $list["$i"-1] ^= $list["$i"];
            $list["$i"]   ^= $list["$i"-1];
            $i--;
            if ($i == 0) {$i = 1;}
        }
    }
    return $list;
}
?>

Python

def gnome_sort(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

Ruby

def gnome_sort(list)
    i = 1
    while i < list.length()
        if list[i-1] <= list[i]
            i += 1
        else
            list[i], list[i-1] = list[i-1], list[i]
            i -= 1
            if i == 0
                i = 1
            end
        end
    end
    return list
end

External link

• Gnome sort