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!
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. :)
@Jussi: In my solution, ties cause an infinite loop. Oops!
@Praxis, I suspect mine does the same.
Here’s a solution in C.
Output:
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:
Since I didn’t see a Python Solution: