Gnome Sort
July 29, 2016
We store the array of flower pots as two lists, one behind the gnome and one before him; the gnome is standing next to the head of the “before” list:
(define (gnome-sort lt? xs)
(let loop ((behind (list)) (before xs))
(display behind) (display " ")
(display before) (newline)
(cond ((null? before)
(reverse behind))
((null? behind)
(loop (list (car before))
(cdr before)))
((lt? (car behind) (car before))
(loop (cons (car before) behind)
(cdr before)))
(else (loop (cdr behind)
(cons (car before)
(cons (car behind)
(cdr before))))))))
We left the debugging output so you can see what happens:
> (gnome-sort < '(4 1 2 5 3)) () (4 1 2 5 3) (4) (1 2 5 3) () (1 4 2 5 3) (1) (4 2 5 3) (4 1) (2 5 3) (1) (2 4 5 3) (2 1) (4 5 3) (4 2 1) (5 3) (5 4 2 1) (3) (4 2 1) (3 5) (2 1) (3 4 5) (3 2 1) (4 5) (4 3 2 1) (5) (5 4 3 2 1) () (1 2 3 4 5)
That’s O(n) in the best case, when the input is sorted or nearly-sorted, and O(n2) when the input is in reverse order; you might want to watch what happens when you sort (5 4 3 2 1). You can run the program at http://ideone.com/1fHJxy.
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