Gnome sort

Gnome sort
	Visualisation of Gnome sort
Class	Sorting algorithm
Data structure	Array
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity	auxiliary

Gnome sort (nicknamed stupid sort) is a variation of the insertion sort sorting algorithm that does not use nested loops. Gnome sort was known for a long time and used without naming it explicitly.^[1] It was then popularized by Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Engineering at Sharif University of Technology)^[2] in 2000. The sort was first called stupid sort^[3] (not to be confused with bogosort), and then later described by Dick Grune and named gnome sort.^[4]

Gnome sort performs at least as many comparisons as insertion sort and has the same asymptotic run time 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.^[5]^{[note 1]}

Dick Grune described the sorting method with the following story:^[4]

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

Pseudocode

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

Notes

^ Almost sorted means that each item in the list is not far from its proper position (not farther than some small constant distance).

References

^ Singer, Michael (1980). "PDP-11 assembler language programming and machine organization". New York, US: John Wiley & Sons. p. 47.
^ Hamid, Sarbazi-Azad. "Hamid Sarbazi-Azad profile page". Archived from the original on 2018-10-16. Retrieved October 16, 2018.
^ Sarbazi-Azad, Hamid (2 October 2000). "Stupid Sort: A new sorting algorithm" (PDF). Newsletter (599). Computing Science Department, Univ. of Glasgow: 4. Archived (PDF) from the original on 7 March 2012. Retrieved 25 November 2014.
^ ^a ^b "Gnome Sort - The Simplest Sort Algorithm". Dickgrune.com. 2000-10-02. Archived from the original on 2017-08-31. Retrieved 2017-07-20.
^ Paul E. Black. "gnome sort". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Archived from the original on 2011-08-11. Retrieved 2011-08-20.

External links

Gnome sort

[6] Almost sorted means that each item in the list is not far from its proper position (not farther than some small constant distance).

[1] Singer, Michael (1980). "PDP-11 assembler language programming and machine organization". New York, US: John Wiley & Sons. p. 47.

[2] Hamid, Sarbazi-Azad. "Hamid Sarbazi-Azad profile page". Archived from the original on 2018-10-16. Retrieved October 16, 2018.

[3] Sarbazi-Azad, Hamid (2 October 2000). "Stupid Sort: A new sorting algorithm" (PDF). Newsletter (599). Computing Science Department, Univ. of Glasgow: 4. Archived (PDF) from the original on 7 March 2012. Retrieved 25 November 2014.

[DGrune-4] "Gnome Sort - The Simplest Sort Algorithm". Dickgrune.com. 2000-10-02. Archived from the original on 2017-08-31. Retrieved 2017-07-20.

[5] Paul E. Black. "gnome sort". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Archived from the original on 2011-08-11. Retrieved 2011-08-20.

[1]

[2]

[3]

[4]

[5]

[note 1]