Algorithm Implementation/Sorting/Gnome sort

C edit

void gnome_sort(int *array, int size){ 
   int i, 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++ edit

#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++ using bidirectional iterators edit

#include <algorithm> // for std::iter_swap

template <typename Iterator>
void gnome_sort(Iterator begin, Iterator end)
{
    Iterator current = begin;
    Iterator before_current;

    while (current != end)
    {
        if (current == begin || *before_current <= *current)
        {
            ++current;
        }
        else
        {
            std::iter_swap(before_current, current);
            --current;
        }
        before_current = current;
        --before_current;
    }
}

Optimized C++ using iterators edit

#include <algorithm> // for std::iter_swap
#include <iterator> // for std::advance

template <typename Iterator>
void gnome_sort(Iterator begin, Iterator end)
{
    Iterator current = begin;
    Iterator before_current;
    size_t step = 1;

    while (current != end)
    {
        if (current == begin || *before_current <= *current)
        {
            std::advance(current, step); // possible leap optimization
            step = 1;
        }
        else
        {
            std::iter_swap(before_current, current);
            --current;
            ++step;
        }
        before_current = current;
        --before_current;
    }
}

The optimized version makes the "gnome" (represented by the 'current' iterator here) leap back to the right i.e. to the place where it needed to swap the flower pots on its farthest reached position so far. This also avoids redundant comparisons. On average the optimization results in cutting the time by one/third on a modern x86 machine. (A wise gnome sort? :). However, the optimization works best if the iterators are random access iterators. Otherwise the algorithm works almost like the non-optimized version - it still avoids redundant comparisons though.

C# edit

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 edit

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

Java edit

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

JavaScript edit

function gnomeSort(sortMe) {
   i=0;
   while (i < sortMe.length) {
      if (i==0||sortMe[i-1] <= sortMe[i]) {
         i++;
      } else {
         tmp=sortMe[i];
         sortMe[i]=sortMe[i-1];
         sortMe[--i]=tmp;
      }
   }
}

LavishScript edit

This sorts an scope-accessible index:objectype (IndexName) passed by variable name, sorting by MemberName, which should be a numeric member of objecttype.

method Gnomesort(string IndexName, string MemberName)
{
  variable int i = 1

  while ${i} <= ${${IndexName}.Used}
  {
    if ( ${i} == 1 ) || ${${IndexName}[${Math.Calc[${i}-1]}].${MemberName}} <= ${${IndexName}[${i}].${MemberName}}
    {
      i:Inc
    }
    else
    {
      ${IndexName}:Swap[${i}, ${Math.Calc[${i}-1]}]
      i:Dec
    }
  }
}

Perl edit

sub gnome_sort(@) { 
    my @list  = @_;
    my $size  = scalar(@list);
    my $right = 1;
    while ( $right < $size ) {
        my $left = $right - 1;
        if ( $list[$left] <= $list[$right] ) {
            $right++;
        }
        else {
            @list[ $left, $right ] = @list[ $right, $left ];
            $right-- if $right > 1;
        }
    }
    return @list;
}

Phix edit

function gnomeSort(sequence s)
integer i = 1, j = 2
    while i<length(s) do
        if s[i]<=s[i+1] then
            i = j
            j += 1
        else
            {s[i],s[i+1]} = {s[i+1],s[i]}
            i -= 1
            if i = 0 then
                i = j
                j += 1
            end if
        end if
    end while
    return s
end function

PHP edit

<?php 
function gnome_sort($list) 
{ 
    for ($i = 1; $i < count($list);) 
    { 
        if ($list[$i-1] <= $list[$i]) {$i++;} 
        else 
        { 
            $temp = $list[$i]; 
            $list[$i] = $list[$i-1]; 
            $list[$i-1] = $temp; 
            $i--; 
            if ($i == 0) {$i = 1;} 
        } 
    } 
    return $list; 
}
?>

Python edit

def gnomeSort(items):
    i = 0
    n = len(items)
    while i < n:
        if i and items[i] < items[i-1]:
            items[i], items[i-1] = items[i-1], items[i]
            i -= 1
        else:
            i += 1
    return items

def teleportingGnomeSort(items):
    i = j = 0
    n = len(items)
    while i < n:
        if i and items[i] < items[i-1]:
            items[i], items[i-1] = items[i-1], items[i]
            i -= 1
        else:
            if i < j: # teleport!
                i = j
            j = i = i+1
    return items

Ruby edit

module GnomeSort
  def self.sort(keys)
    sort!(keys.clone)
  end
  
  def self.sort!(keys)
    i, j = 1, 2
    while i < keys.size
      if keys[i-1] <= keys[i]
        i, j = j, j+1
      else
        keys[i-1], keys[i] = keys[i], keys[i-1]
        i -= 1 if i > 1
      end
    end
    keys
  end
end