Gnome sort - Misplaced Pages

Sorting algorithm

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Gnome sort" – news · newspapers · books · scholar · JSTOR (August 2010) (Learn how and when to remove this message)

Gnome sort
Visualisation of Gnome sort
Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^{2})$
Best-case performance	$O(n)$
Average performance	$O(n^{2})$
Worst-case space complexity	$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) 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.

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.

Dick Grune described the sorting method with the following story:

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

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 >= a):
           pos := pos + 1
       else:
           swap a and a
           pos := pos - 1

Example

Given an unsorted array, a = , 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.

`pos`	Condition in effect	Action to take
0	pos == 0	increment pos
1	a < a	swap, decrement pos
0	pos == 0	increment pos
1	a ≥ a	increment pos
2	a < a	swap, decrement pos
1	a < a	swap, decrement pos
0	pos == 0	increment pos
1	a ≥ a	increment pos
2	a ≥ a	increment pos:
3	a < a	swap, decrement pos
2	a ≥ a	increment pos
3	a ≥ a	increment pos
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". 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 (599). Computing Science Department, Univ. of Glasgow: 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.

External links

Gnome sort

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort
Impractical sorts	Stooge sort Slowsort Bogosort

Categories: