# Gnome Sort

Gnome Sort is a sorting algorithm that emulates the movement of a Turing machine – having the pointer only be able to move one step at a time.

## How Gnome Sort works

Gnome Sort is a variation of Insertion Sort, but with the limitation of not being able to shift the pointer more than one step at a time. This make the visualisation look like there is a gnome moving back and forth along the array carrying over one item at a time.

### Example

The array starts with the leftmost item being considered a ‘sorted’ sub-array of size 1. The second item is then picked up and moved leftward until it finds its correct position within the sorted subarray. At this point, Gnome Sort is identical to Insertion sort.

Once this is done, the elements are compared rightwards until an element is found that is out of order. This will eventually put the pointer at the next unsorted element at which point we can repeat the cycle.

The entire list is sorted when the rightward crawl overcomes the length of the array.

## Visualisation

TBD

## Time complexity

Gnome Sort uses comparisons and swaps to sort the array

### Comparisons

The time complexity for comparisons is n^{2}/2, which makes sense since each step takes twice as long as Insertion Sort.

### Swaps

Swaps are on the same order as well but half as much, n^{2}/4.This is because when the gnome move right, no swaps are taking place.

### Distribution

This is how the comparisons and swaps are distributed for this sorting algorithm of size 100 for 1,000,000 sorts.

Mode: 5,023

Mean: 5,046

Std dev: 335

Max: 6,622

Min: 3,482

Mode: 2,457

Mean: 2,475

Std dev: 167

Max: 3,264

Min: 1,692

These distributions aren’t anything out of the ordinary. Just two normal distributions.

## C code

```
void gnome_sort(int *p, int len) {
int i = 1;
while (i < len) {
if (i == 0) {
// Reached left end, move right and skip
i++;
continue;
} else if (is_greater_than_p(&p[i-1], &p[i]) && i != len) {
// Swap pots and move leftwards
swap(&p[i], &p[i-1]);
i--;
} else {
// Move rightwards
i++;
}
}
}
```