## 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.

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
```