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.
Programming Praxis 
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";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) endbut 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. :)
@Jussi: In my solution, ties cause an infinite loop. Oops!
@Praxis, I suspect mine does the same.
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:
(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.
Isn’t this just a variant of insertion sort?
> “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.
@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:
(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)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