Sorting algorithms/Gnome sort

Sorting algorithms/Gnome sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

This page uses content from Wikipedia. The original article was at Sorting algorithms/Gnome sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

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 pseudocode for the algorithm is:

function gnomeSort(a[0..size-1])
    i := 1
    j := 2
    while i < size do
        if a[i-1] <= a[i] then
            // for descending sort, use >= for comparison
            i := j
            j := j + 1 
        else
            swap a[i-1] and a[i]
            i := i - 1
            if i = 0 then
                i := j
                j := j + 1
            endif
        endif
    done

Task: implement the Gnome sort in your language to sort an array (or list) of numbers.

Ada

This example is a generic procedure for constrained array types. <lang Ada>generic

  type Element_Type is private;
  type Index is (<>);
  type Collection is array(Index) of Element_Type;
  with function "<=" (Left, Right : Element_Type) return Boolean is <>;

procedure Gnome_Sort(Item : in out Collection);</lang>

<lang Ada>procedure Gnome_Sort(Item : in out Collection) is

  procedure Swap(Left, Right : in out Element_Type) is
     Temp : Element_Type := Left;
  begin
     Left := Right;
     Right := Temp;
  end Swap;
  
  I : Integer := Index'Pos(Index'Succ(Index'First));
  J : Integer := I + 1;

begin

  while I <= Index'Pos(Index'Last) loop
     if Item(Index'Val(I - 1)) <= Item(Index'Val(I)) then
        I := J;
        J := J + 1;
     else
        Swap(Item(Index'Val(I - 1)), Item(Index'Val(I)));
        I := I - 1;
        if I = Index'Pos(Index'First) then
           I := J;
           J := J + 1;
        end if;
     end if;
  end loop;

end Gnome_Sort;</lang> Usage example: <lang Ada>with Gnome_Sort; with Ada.Text_Io; use Ada.Text_Io;

procedure Gnome_Sort_Test is

  type Index is range 0..9;
  type Buf is array(Index) of Integer;
  procedure Sort is new Gnome_Sort(Integer, Index, Buf);
  A : Buf := (900, 700, 800, 600, 400, 500, 200, 100, 300, 0);

begin

  for I in A'range loop
     Put(Integer'Image(A(I)));
  end loop;
  New_Line;
  Sort(A);
  for I in A'range loop
     Put(Integer'Image(A(I)));
  end loop;
  New_Line;

end Gnome_Sort_Test;</lang>

ALGOL 68

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

Works with: ELLA ALGOL 68 version Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386

<lang algol>MODE SORTSTRUCT = CHAR;

PROC inplace gnome sort = (REF[]SORTSTRUCT list)REF[]SORTSTRUCT: BEGIN

 INT i:=LWB list + 1, j:=LWB list + 2;
 WHILE i <= UPB list DO
   IF list[i-1] <= list[i] THEN
     i := j; j+:=1
   ELSE
     SORTSTRUCT swap = list[i-1]; list[i-1]:= list[i]; list[i]:= swap;
     i-:=1;
     IF i=LWB list THEN i:=j; j+:=1 FI
   FI
 OD;
 list

END;

PROC gnome sort = ([]SORTSTRUCT seq)[]SORTSTRUCT:

 in place gnome sort(LOC[LWB seq: UPB seq]SORTSTRUCT:=seq);

[]SORTSTRUCT char array data = "big fjords vex quick waltz nymph"; print((gnome sort(char array data), new line))</lang> Output:

     abcdefghiijklmnopqrstuvwxyz

AutoHotkey

contributed by Laszlo on the ahk forum <lang AutoHotkey>MsgBox % GnomeSort("") MsgBox % GnomeSort("xxx") MsgBox % GnomeSort("3,2,1") MsgBox % GnomeSort("dog,000000,xx,cat,pile,abcde,1,cat,zz,xx,z")

GnomeSort(var) {  ; SORT COMMA SEPARATED LIST

  StringSplit a, var, `,                ; make array, size = a0
  i := 2, j := 3
  While i <= a0 {                       ; stop when sorted
     u := i-1
     If (a%u% < a%i%)                   ; search for pairs to swap
        i := j, j := j+1
     Else {                             ; swap
        t := a%u%, a%u% := a%i%, a%i% := t
        If (--i = 1)                    ; restart search
           i := j, j++
     }
  }
  Loop % a0                             ; construct string from sorted array
     sorted .= "," . a%A_Index%
  Return SubStr(sorted,2)               ; drop leading comma

}</lang>

BASIC

Works with: QuickBasic version 4.5

Translation of: C

<lang qbasic>dim a(0 to n-1) as integer '...more code... sort: i = 1 j = 2

while(i < ubound(a) - lbound(a))

 if a(i-1) <= a(i) then
   i = j
   j = j + 1
 else 
   swap a(i-1), a(i)
   i = i - 1
   if i = 0 then
      i = j
      j = j + 1
   end if
 end if

wend</lang>

C

This algorithm sorts in place modifying the passed array (of n integer numbers).

<lang c>#define swap_(I,J) do { int t_; t_ = a[(I)]; \

     a[(I)] = a[(J)]; a[(J)] = t_; } while(0)

void gnome_sort(int *a, int n) {

 int i=1, j=2;

 while(i < n) {
   if ( a[i-1] <= a[i] ) {
     i = j; j++;
   } else {
     swap_(i-1, i);
     i--;
     i = (i==0) ? j++ : i;
   }
 }

}

1. undef swap_</lang>

C++

Compiler: g++ (version 4.3.2 20081105 (Red Hat 4.3.2-7))

<lang cpp>#include <algorithm>

1. include <iterator>

template<typename RandomAccessIterator> void gnomeSort(RandomAccessIterator begin, RandomAccessIterator end) {

 RandomAccessIterator i = begin + 1;
 RandomAccessIterator j = begin + 2;

 while(i < end) {
   if(*(i - 1) <= *i) {
     i = j;
     ++j;
   } else {
     std::iter_swap(i - 1, i);
     --i;
     if(i == begin) {
       i = j;
       ++j;
     }
   }
 }

} </lang>

Common Lisp

<lang lisp>(defun gnome-sort (array predicate &aux (length (length array)))

 (do ((position (min 1 length)))
     ((eql length position) array)
   (cond
    ((eql 0 position)
     (incf position))
    ((funcall predicate
              (aref array position)
              (aref array (1- position)))
     (rotatef (aref array position)
              (aref array (1- position)))
     (decf position))
    (t (incf position)))))</lang>

E

<lang e>def gnomeSort(array) {

   var size := array.size()
   var i := 1
   var j := 2
   while (i < size) {
       if (array[i-1] <= array[i]) {
           i := j
           j += 1
       } else {
           def t := array[i-1]
           array[i-1] := array[i]
           array[i] := t
           i -= 1
           if (i <=> 0) {
               i := j
               j += 1
           }
       }
   }

}</lang>

<lang e>? def a := [7,9,4,2,1,3,6,5,0,8].diverge()

1. value: [7, 9, 4, 2, 1, 3, 6, 5, 0, 8].diverge()

? gnomeSort(a) ? a

1. value: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].diverge()</lang>

Fortran

Works with: Fortran version 90 and later

<lang fortran>program example

 implicit none

 integer :: array(8) = (/ 2, 8, 6, 1, 3, 5, 4, 7 /)

 call Gnomesort(array)
 write(*,*) array

contains

subroutine Gnomesort(a)

 integer, intent(in out) :: a(:)
 integer :: i, j, temp

 i = 2
 j = 3
 do while (i <= size(a))
   if (a(i-1) <= a(i)) then
     i = j
     j = j + 1
   else
     temp = a(i-1)
     a(i-1) = a(i)
     a(i) = temp
     i = i -  1
     if (i == 1) then
       i = j
       j = j + 1
     end if
   end if
 end do

end subroutine Gnomesort

end program example</lang>

J

<lang J> position=: 0 {.@I.@, [ swap=: ] A.~ *@position * #@[ !@- <:@position gnome=: swap~ 2 >/\ ] gnomes=: gnome^:_ </lang>

Note 1: this implementation of swap is actually rather silly, and will not work on long lists. A better implementation would be: <lang J>swap=: position (] {~ _1 0 + [)`(0 _1 + [)`]}^:(*@[) ]</lang>

Note 2: this implementation only works for domains where > is defined (in J, "greater than" only works on numbers). To work around this issue, you could define: <lang J>gt=: -.@(-: /:~)@,&< gnome=: swap~ 2 gt/\ ]</lang>

Note 3: this implementation does not return intermediate results. If you want them, you could use <lang J>gnomeps=: gnome^:a:</lang>

Note 4: gnomeps just shows intermediate results and does not show the gnome's position. You can extract the gnome's position using an expression such as <lang J>2 ~:/\ gnomeps</lang>.

Java

Translation of: C

<lang java>public static void gnomeSort(int[] a) {

 int i=1;
 int j=2;

 while(i < a.length) {
   if ( a[i-1] <= a[i] ) {
     i = j; j++;
   } else {
     int tmp = a[i-1];
     a[i-1] = a[i];
     a[i--] = tmp;
     i = (i==0) ? j++ : i;
   }
 }

}</lang>

Metafont

<lang metafont>def gnomesort(suffix v)(expr n) = begingroup save i, j, t;

 i := 1; j := 2;
 forever: exitif not (i < n);
   if v[i-1] <= v[i]:
     i := j; j := j + 1;
   else:
     t := v[i-1];
     v[i-1] := v[i];
     v[i] := t;
     i := i - 1;
     i := if i=0: j; j := j + 1 else: i fi;
   fi
 endfor

endgroup enddef;</lang>

<lang metafont>numeric a[]; for i = 0 upto 9: a[i] := uniformdeviate(40); message decimal a[i]; endfor message char10;

gnomesort(a, 10); for i = 0 upto 9: message decimal a[i]; endfor end</lang>

OCaml

<lang ocaml># let gnome_sort a =

   let i = ref 1 
   and j = ref 2 in
   while !i < Array.length a do
     if a.(!i-1) <= a.(!i) then
     begin
       i := !j;
       j := !j + 1;
     end else begin
       swap a (!i-1) (!i);
       i := !i - 1;
       if !i = 0 then begin
         i := !j;
         j := !j + 1;
       end;
     end;
   done;
 ;;

val gnome_sort : 'a array -> unit = <fun>

1. let a = [| 7; 9; 4; 2; 1; 3; 6; 5; 0; 8; |] ;;

val a : int array = [|7; 9; 4; 2; 1; 3; 6; 5; 0; 8|]

1. gnome_sort a ;;

- : unit = ()

1. a ;;

- : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]</lang>

Octave

<lang octave>function s = gnomesort(v)

 i = 2; j = 3;
 while ( i <= length(v) )
   if ( v(i-1) <= v(i) )
     i = j;
     j++;
   else
     t = v(i-1);
     v(i-1) = v(i);
     v(i) = t;
     i--;
     if ( i == 1 )

i = j; j++;

     endif
   endif
 endwhile
 s = v;

endfunction</lang>

<lang octave>v = [7, 9, 4, 2, 1, 3, 6, 5, 0, 8]; disp(gnomesort(v));</lang>

Pascal

<lang pascal>procedure gnomesort(var arr : Array of Integer; size : Integer); var

  i, j, t	: Integer;

begin

  i := 1;
  j := 2;
  while i < size do begin
     if arr[i-1] <= arr[i] then
     begin

i := j; j := j + 1

     end
     else begin

t := arr[i-1]; arr[i-1] := arr[i]; arr[i] := t; i := i - 1; if i = 0 then begin i := j; j := j + 1 end

     end
  end;

end;</lang>

Perl

<lang perl>use strict;

sub gnome_sort {

   my @a = @_;

   my $size = scalar(@a);
   my $i = 1;
   my $j = 2;
   while($i < $size) {

if ( $a[$i-1] <= $a[$i] ) { $i = $j; $j++; } else { @a[$i, $i-1] = @a[$i-1, $i]; $i--; if ($i == 0) { $i = $j; $j++; } }

   }
   return @a;

}</lang>

<lang perl>my @arr = ( 10, 9, 8, 5, 2, 1, 1, 0, 50, -2 ); print "$_\n" foreach gnome_sort( @arr );</lang>

Python

<lang python>>>> def gnomesort(a): i,j,size = 1,2,len(a) while i < size: if a[i-1] <= a[i]: i,j = j, j+1 else: a[i-1],a[i] = a[i],a[i-1] i -= 1 if i == 0: i,j = j, j+1 return a

>>> gnomesort([3,4,2,5,1,6]) [1, 2, 3, 4, 5, 6] >>> </lang>

Ruby

<lang ruby>class Array

 def gnomesort!
   i, j = 1, 2
   while i < length
     if self[i-1] <= self[i]
       i, j = j, j+1
     else
       self[i-1], self[i] = self[i], self[i-1]
       i -= 1
       if i == 0
         i, j = j, j+1
       end
     end
   end
   self
 end

end ary = [7,6,5,9,8,4,3,1,2,0] ary.gnomesort!

1. => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</lang>

Smalltalk

<lang smalltalk>Smalltalk at: #gnomesort put: nil.

"Utility" OrderedCollection extend [

 swap: a with: b [ |t|
     t := self at: a.
     self at: a put: b.
     self at: b put: t
 ]

].

"Gnome sort as block closure" gnomesort := [ :c |

 |i j|
 i := 2. j := 3.
 [ i <= (c size) ]
   whileTrue: [
      (c at: (i-1)) <= (c at: i)
         ifTrue: [
            i := j copy.
            j := j + 1.
         ]
         ifFalse: [
            c swap: (i-1) with: i.
            i := i - 1.
            i == 1
              ifTrue: [
                 i := j copy.
                 j := j + 1
              ]
         ]
   ]

].</lang>

Testing

<lang smalltalk>|r o| r := Random new. o := OrderedCollection new.

1 to: 10 do: [ :i | o add: (r between: 0 and: 50) ].

gnomesort value: o.

1 to: 10 do: [ :i | (o at: i) displayNl ].</lang>

Tcl

Uses struct::list package from

Library: tcllib

<lang tcl>package require Tcl 8.5 package require struct::list

proc gnomesort {a} {

   set i 1
   set j 2
   set size [llength $a]
   while {$i < $size} {
       if {[lindex $a [expr {$i - 1}]] <= [lindex $a $i]} {
           set i $j
           incr j
       } else {
           struct::list swap a [expr {$i - 1}] $i
           incr i -1
           if {$i == 0} {
               set i $j
               incr j
           }
       }
   }
   return $a

}

puts [gnomesort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>

Ursala

The function is parameterized by a relational predicate and operates on a list. The algorithm is to scan forward until finding an item out of order, bubble it backwards to its proper position and resume scanning forward from where it was. <lang Ursala> gnome_sort "p" =

@NiX ^=lx -+ # iteration

  ~&r?\~& @lNXrX ->llx2rhPlrPCTxPrtPX~&lltPlhPrCXPrX ~&ll&& @llPrXh not "p",    # backward bubble
  ->~&rhPlCrtPX ~&r&& ~&lZ!| @bh "p"+-                                          # forward scan

</lang> Most of the code is wasted on dull but unavoidable stack manipulations. Here is a test program using the lexical partial order relation. <lang Ursala>

1. import std
2. cast %s

t = gnome_sort(lleq) 'dfijhkwlawfkjnksdjnoqwjefgflkdsgioi' </lang> output:

'adddeffffgghiiijjjjkkkkllnnooqsswww'