Gnome sort

Template:Infobox Algorithm 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.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> It was then popularized by Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Engineering at Sharif University of Technology)<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> in 2000. The sort was first called stupid sort<ref>Template:Cite journal</ref> (not to be confused with bogosort), and then later described by Dick Grune and named gnome sort.<ref name="DGrune">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

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.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref group="note">Almost sorted means that each item in the list is not far from its proper position (not farther than some small constant distance).</ref>

Dick Grune described the sorting method with the following story:<ref name="DGrune" />

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

External links

• Gnome sort