Gnome sort explained

Class:Sorting algorithm
Data:Array
Time:

O(n2)

Best-Time:

O(n)

Average-Time:

O(n2)

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 originally proposed by Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Engineering at Sharif University of Technology)[1] in 2000. The sort was first called stupid sort[2] (not to be confused with bogosort), and then later described by Dick Grune and named gnome sort.[3]

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(n2) but tends towards O(n) if the list is initially almost sorted.[4] [5]

Dick Grune described the sorting method with the following story:

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 arrayposCondition in effectAction 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

Notes and References

  1. Web site: Hamid Sarbazi-Azad profile page. Hamid. Sarbazi-Azad. https://web.archive.org/web/20181016164904/http://sharif.edu/~azad/#. 2018-10-16. live. October 16, 2018.
  2. Sarbazi-Azad . Hamid . 2 October 2000 . Stupid Sort: A new sorting algorithm . Newsletter . Computing Science Department, Univ. of Glasgow . 599 . 4 . 25 November 2014 . https://web.archive.org/web/20120307235904/http://sina.sharif.edu/~azad/stupid-sort.PDF . 7 March 2012 . live.
  3. Web site: Gnome Sort - The Simplest Sort Algorithm . Dickgrune.com . 2000-10-02 . 2017-07-20 . https://web.archive.org/web/20170831222005/https://dickgrune.com/Programs/gnomesort.html# . 2017-08-31 . live .
  4. Web site: gnome sort . Dictionary of Algorithms and Data Structures . U.S. National Institute of Standards and Technology . Paul E. Black . 2011-08-20 . https://web.archive.org/web/20110811012120/http://xlinux.nist.gov/dads//HTML/gnomeSort.html# . 2011-08-11 . live.
  5. Almost sorted means that each item in the list is not far from its proper position (not farther than some small constant distance).