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

|time=$O(n^2)$

|best-time=$O(n)$

|average-time= $O(n^2)$

|space= $O(1)$ 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.{{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}} It was then popularized by Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Engineering at Sharif University of Technology){{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}} in 2000. The sort was first called stupid sort{{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

}} (not to be confused with bogosort), and then later described by Dick Grune and named gnome sort.{{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 }}

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.{{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

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

Dick Grune described the sorting method with the following story:

{{quote|

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.

|sign=| source="Gnome Sort - The Simplest Sort Algorithm". Dickgrune.com}}