Gnome sort

Gnome sort

Visualisation of Gnome sort
Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^{2})$
Best-case performance	$O(n)$
Average performance	$O(n^{2})$
Worst-case space complexity	$O(1)$ auxiliary

Gnome sort (dubbed stupid sort) is a variation of the insertion sort sorting algorithm that does not use nested loops. Gnome sort was originally proposed by Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Engineering at Sharif University of Technology) in 2000. The sort was first called stupid sort (not to be confused with bogosort), and then later described by Dick Grune and named gnome sort.

Gnome sort performs the at least as many comparisons as insertion sort and has the same asymptotic runtime characteristics. Gnome sort works by building a sorted list one element at a time, getting each item to the proper place in a series of swaps. The average running time is O(n²) but tends towards O(n) if the list is initially almost sorted.

The algorithm finds the first place where two adjacent elements are in the wrong order and swaps them. It takes advantage of the fact that performing a swap can only introduce a new out-of-order adjacent pair next to the previously swapped elements. It does not assume that elements forward of the current position are sorted, so it only needs to check the position directly previous to the swapped elements.

Description

Dick Grune described the sorting method with the following story:

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter).
Here is how a garden gnome sorts a line of flower pots.
Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise, he swaps them and steps one pot backward.
Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

— "Gnome Sort - The Simplest Sort Algorithm". Dickgrune.com

Code

Here is pseudocode for the gnome sort using a zero-based array:

procedure gnomeSort(a[]):
    pos := 0
    while pos < length(a):
        if (pos == 0 or a[pos] >= a[pos-1]):
            pos := pos + 1
        else:
            swap a[pos] and a[pos-1]
            pos := pos - 1

Example

Given an unsorted array, a = [5, 3, 2, 4], the gnome sort takes the following steps during the while loop. The current position is highlighted in bold and indicated as a value of the variable pos.

Current array	pos	Condition in effect	Action to take
[5, 3, 2, 4]	0	pos == 0	increment pos
[5, 3, 2, 4]	1	a[pos] < a[pos-1]	swap, decrement pos
[3, 5, 2, 4]	0	pos == 0	increment pos
[3, 5, 2, 4]	1	a[pos] ≥ a[pos-1]	increment pos
[3, 5, 2, 4]	2	a[pos] < a[pos-1]	swap, decrement pos
[3, 2, 5, 4]	1	a[pos] < a[pos-1]	swap, decrement pos
[2, 3, 5, 4]	0	pos == 0	increment pos
[2, 3, 5, 4]	1	a[pos] ≥ a[pos-1]	increment pos
[2, 3, 5, 4]	2	a[pos] ≥ a[pos-1]	increment pos:
[2, 3, 5, 4]	3	a[pos] < a[pos-1]	swap, decrement pos
[2, 3, 4, 5]	2	a[pos] ≥ a[pos-1]	increment pos
[2, 3, 4, 5]	3	a[pos] ≥ a[pos-1]	increment pos
[2, 3, 4, 5]	4	pos == length(a)	finished

External links

• Gnome sort