Editing Gnome sort

{{Short description|Sorting algorithm}}
{{Refimprove|date=August 2010}}

{{Infobox Algorithm
|name={{PAGENAMEBASE}}|class=[[Sorting algorithm]]
|image=Visualization of Gnome sort.gif
|caption=Visualisation of Gnome sort
|data=[[Array data structure|Array]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math>
|average-time= <math>O(n^2)</math>
|space= <math>O(1)</math> 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.<ref>{{Cite web| url=https://archive.org/details/pdp11assemblerlanguageprogrammingandmachineorganization/page/n60/mode/1up| title=PDP-11 assembler language programming and machine organization| last=Singer|first=Michael| page=47| publisher=[[John Wiley & Sons]]| location=New York, US| date=1980}}</ref> It was then popularized by [[Iran]]ian computer scientist [[Hamid Sarbazi-Azad]] (professor of Computer Science and Engineering at [[Sharif University of Technology]])<ref>{{Cite web|url=http://sharif.edu/~azad/|title=Hamid Sarbazi-Azad profile page|last=Hamid|first=Sarbazi-Azad|archive-url=https://web.archive.org/web/20181016164904/http://sharif.edu/~azad/|archive-date=2018-10-16|url-status=live|access-date=October 16, 2018}}</ref> in 2000. The sort was first called ''stupid sort''<ref>{{cite journal
 |last         = Sarbazi-Azad
 |first        = Hamid
 |date         = 2 October 2000
 |title        = Stupid Sort: A new sorting algorithm
 |url          = http://sina.sharif.edu/~azad/stupid-sort.PDF
 |journal      = Newsletter
 |publisher    = Computing Science Department, Univ. of Glasgow
 |issue        = 599
 |page         = 4
 |access-date   = 25 November 2014
 |archive-url  = https://web.archive.org/web/20120307235904/http://sina.sharif.edu/~azad/stupid-sort.PDF
 |archive-date = 7 March 2012
 |url-status   = live
}}</ref> (not to be confused with [[bogosort]]), and then later described by [[Dick Grune]] and named ''gnome sort''.<ref name="DGrune">{{cite web |url=http://www.dickgrune.com/Programs/gnomesort.html |title=Gnome Sort - The Simplest Sort Algorithm |website=Dickgrune.com |date=2000-10-02 |access-date=2017-07-20 |archive-url=https://web.archive.org/web/20170831222005/https://dickgrune.com/Programs/gnomesort.html |archive-date=2017-08-31 |url-status=live }}</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 [[Big O notation|''O'']](''n''<sup>2</sup>) but tends towards ''O''(''n'') if the list is initially almost sorted.<ref>{{cite web
 |url          = http://xlinux.nist.gov/dads/HTML/gnomeSort.html
 |title        = gnome sort
 |work         = Dictionary of Algorithms and Data Structures
 |publisher    = U.S. National Institute of Standards and Technology
 |author       = Paul E. Black
 |access-date   = 2011-08-20
 |archive-url  = https://web.archive.org/web/20110811012120/http://xlinux.nist.gov/dads//HTML/gnomeSort.html
 |archive-date = 2011-08-11
 |url-status     = live
}}</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" />

{{quote|
Gnome Sort is based on the technique used by the standard Dutch [[garden gnome|Garden Gnome]] (Du.: [[:nl:tuinkabouter|tuinkabouter]]). <br />
Here is how a garden gnome sorts a line of [[flowerpot|flower pots]]. <br />
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. <br />
Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.
|sign=| source="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 <code>pos</code>.

{|    class="wikitable"
|-
! Current array
! <code>pos</code>
! 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==
{{reflist|group=note}}
==References==
{{Reflist}}

==External links==
{{wikibooks|Algorithm implementation|Sorting/Gnome_sort|Gnome sort}}
* [http://dickgrune.com/Programs/gnomesort.html Gnome sort]

{{sorting}}

{{DEFAULTSORT:Gnome Sort}}
[[Category:Comparison sorts]]
[[Category:Stable sorts]]