This article needs additional citations for verification. (August 2010)
|Worst-case space complexity||auxiliary|
Gnome sort (dubbed stupid sort) is a sorting algorithm originally proposed by Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Engineering at Sharif University of Technology) in 2000. The sort was first called stupid sort (not to be confused with bogosort), and then later described by Dick Grune and named gnome sort.
The gnome sort is a sorting algorithm which is similar to insertion sort in that it works with one item at a time but gets the item to the proper place by a series of swaps, similar to a bubble sort. It is conceptually simple, requiring no nested loops. The average running time is O(n2) but tends towards O(n) if the list is initially almost sorted.[note 1]
The algorithm finds the first place where two adjacent elements are in the wrong order and swaps them. It takes advantage of the fact that performing a swap can introduce a new out-of-order adjacent pair next to the previously swapped elements. It does not assume that elements forward of the current position are sorted, so it only needs to check the position directly previous to the swapped elements.
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
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
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
|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|
The gnome sort may be optimized by introducing a variable to store the position before traversing back toward the beginning of the list. With this optimization, the gnome sort would become a variant of the insertion sort.
procedure optimizedGnomeSort(a): for pos in 1 to length(a): gnomeSort(a, pos) procedure gnomeSort(a, upperBound): pos := upperBound while pos > 0 and a[pos-1] > a[pos]: swap a[pos-1] and a[pos] pos := pos - 1
- Almost sorted means that each item in the list is not far from its proper position (not farther than some small constant distance).
- 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. Computing Science Department, Univ. of Glasgow (599): 4. Archived (PDF) from the original on 7 March 2012. Retrieved 25 November 2014.
- "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.
|The Wikibook Algorithm implementation has a page on the topic of: Gnome sort|