Gnome sort
 Visualisation of Gnome sort | |
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | [math]\displaystyle{ O(n^2) }[/math] |
| Best-case performance | [math]\displaystyle{ O(n) }[/math] |
| Average performance | [math]\displaystyle{ O(n^2) }[/math] |
| Worst-case space complexity | [math]\displaystyle{ 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 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][note 1]
Dick Grune described the sorting method with the following story:[3]
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.
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 |
Notes
- ↑ Almost sorted means that each item in the list is not far from its proper position (not farther than some small constant distance).
References
- ↑ Hamid, Sarbazi-Azad. "Hamid Sarbazi-Azad profile page". http://sharif.edu/~azad/.
- ↑ Sarbazi-Azad, Hamid (2 October 2000). "Stupid Sort: A new sorting algorithm". Newsletter (Computing Science Department, Univ. of Glasgow) (599): 4. http://sina.sharif.edu/~azad/stupid-sort.PDF. Retrieved 25 November 2014.
- ↑ 3.0 3.1 "Gnome Sort - The Simplest Sort Algorithm". 2000-10-02. http://www.dickgrune.com/Programs/gnomesort.html.
- ↑ Paul E. Black. "gnome sort". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. http://xlinux.nist.gov/dads/HTML/gnomeSort.html.
External links
 |  |
