Gnome Sort

July 29, 2016

A garden gnome sorts flower pots by the following method:

The gnome looks at the flower pot next to him and the flower pot just behind him. If they are correctly ordered, so the flower pot just behind him is smaller than the flower pot next to him, he steps one pot forward; otherwise, he swaps the two flower pots and steps one pot backward. If there is no flower pot just behind him (thus, he is at the start of the line of flower pots), he steps forward to the next pot. If there is not flower pot next to him (thus, he is at the end of the line of flower pots), he is done.

Your task is to implement a program that sorts by the gnome method. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

11 Responses to “Gnome Sort”

  1. As a bit of perl golf!

    use strict;
    use warnings;
    
    sub gnome_sort {
      my @t=@_;
      for($_=0;$_<$#t;){if($t[$_+1]<$t[$_]){@t[$_+1,$_]=@t[$_,$_+1];$_--if$_;}else{$_++;}}
      return @t;
    }
    
    my @X = map { int rand 40 } 1..100;
    print "@X\n";
    print "@{[gnome_sort(@X)]}\n";
    
  2. Jussi Piitulainen said
    typealias Pot UInt8
    function sort!(pots::Vector{Pot})
        gnome = rand(1:length(pots))
        doing = true
        while doing
            if gnome == 1
                gnome += 1
            elseif gnome > length(pots)
                doing = false
            elseif pots[gnome - 1] < pots[gnome]
                gnome += 1
            else
                pots[gnome - 1], pots[gnome] = pots[gnome], pots[gnome - 1]
                gnome -= 1
    end end end
    
    let pots = rand(UInt8, 8)
        info(pots)
        sort!(pots)
        info(pots)
    end
    

    but this gnome is not instructed to go start at the start of the row, and there seem to be some unattended pots left behind fairly often.

    (How would ties behave? I meant to accept them as ordered but I see now that I forgot. Uh oh. :)

  3. programmingpraxis said

    @Jussi: In my solution, ties cause an infinite loop. Oops!

  4. Jussi Piitulainen said

    @Praxis, I suspect mine does the same.

  5. Daniel said

    Here’s a solution in C.

    #include <stdio.h>
    
    // Sorts in-place.
    void GnomeSort(int array[], int n) {
      int position = 0;
      while (1) {
        // "If there is no flower pot just behind him (thus, he is at the start of
        // the line of flower pots), he steps forward to the next pot."
        if (position == 0) ++position;
    
        // "If there is no flower pot next to him (thus, he is at the end of the
        // line of flower pots), he is done."
        if (position >= n) break;
    
        // "The gnome looks at the flower pot next to him and the flower pot just
        // behind him."
        int next = array[position];
        int behind = array[position-1];
    
        // "If they are correctly ordered, so the flower pot just behind him is
        // smaller than the flower pot next to him, he steps one pot forward."
        if (next >= behind) {
          ++position;
          continue;
        }
    
        // "Otherwise, he swaps the two flower pots and steps one pot backward."
        array[position] = behind;
        array[position-1] = next;
        --position;
      }
    }
    
    void PrintArray(int array[], int n) {
      printf("[");
      for (int i = 0; i < n; i++) {
        if (i > 0) printf(", ");
        printf("%d", array[i]);
      }
      printf("]\n");
    }
    
    int main(int argc, char* argv[]) {
      int array[] = {5, 2, 0, 6, 7, 4, 1, 3, 8, 9};
      int n = sizeof(array) / sizeof(int);
      GnomeSort(array, n);
      PrintArray(array, n);
    }
    

    Output:

    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    
  6. Matt W said
    (define (gnome-sort l)
      (display l) (newline)
      (let loop ((next-to l)
                 (behind '()))
        (cond
          ((null? next-to) behind)
          ((null? behind) (loop (cdr next-to)
                                (cons (car next-to) behind)))
          ((> (car next-to) (car behind)) (loop (cons (car next-to)
                                                      (cons (car behind)
                                                            (cdr next-to)))
                                                (cdr behind)))
          (else (loop (cdr next-to)
                      (cons (car next-to) behind))))))
    

    Heh, checked the reference solution after getting mine done. They look preeetty similar.

  7. matthew said

    Isn’t this just a variant of insertion sort?

  8. Daniel said

    > “Isn’t this just a variant of insertion sort?”

    If the gnome could jump over all the flower pots he swapped with when swapping a pot into place, it would seemingly be insertion sort.

  9. matthew said

    @Daniel: indeed, the sequence of swaps are the same as for a (swap-based) insertion sort, but more comparisons are made as we don’t keep track of the position of the last out of order item.

    Gnomesort is nicely represented as a Markov program (see https://matthewarcus.wordpress.com/2014/01/08/markov-computation/ for explanation & a little interpreter). Here we have some rewrite rules for sorting sequences of two different items A and B, * is the gnome, who stands in-between the flower pots:

    $ cat gnome.mkv
    # Swap out of order
    B*A => *AB
    # Else go right
    *A => A*
    *B => B*
    # Exit gnome, stage right
    * =>.
    # Enter gnome, stage left
      => *
    
    $ ./markov BABAAB < gnome.mkv 
    BABAAB
    *BABAAB
    B*ABAAB
    *ABBAAB
    A*BBAAB
    AB*BAAB
    ABB*AAB
    AB*ABAB
    A*ABBAB
    AA*BBAB
    AAB*BAB
    AABB*AB
    AAB*ABB
    AA*ABBB
    AAA*BBB
    AAAB*BB
    AAABB*B
    AAABBB*
    AAABBB
    
  10. Johan said
    (defun gnome-sort (seq &optional (pos 0))
      (cond ((= pos (length seq)) seq)
            ((= pos 0) (gnome-sort seq 1))
            (t (if (<= (elt seq (1- pos)) (elt seq pos))
                   (gnome-sort seq (1+ pos))
                   (progn
                     (rotatef (elt seq (1- pos)) (elt seq pos))
                     (gnome-sort seq (1- pos)))))))
    
    CL-USER> (let ((list (list 4 3 5 -1 0 55 7)))
               (gnome-sort list))
    (-1 0 3 4 5 7 55)
    
  11. Alex B said

    Since I didn’t see a Python Solution:

    def gnome_sort(seq):
        '''Sort a mutable sequence _in_place_ using gnome sort.'''
    
        # Programming Praxis 2016/7/29
        # https://programmingpraxis.com/2016/07/29/gnome-sort/
        
        pos=0
        while True:
            if pos == 0: # Gnome at start of line -> step forward
                pos += 1
            elif pos == len(seq): # Gnome at end of line -> stop
                break
            elif seq[pos-1] > seq[pos]: # Pot behind bigger -> swap and step back
                seq[pos], seq[pos-1] = seq[pos-1], seq[pos]
                pos -= 1
            elif seq[pos-1] <= seq[pos]: # Pots in order -> step forward
                pos += 1
        return
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: