(algorithm)
Definition: Put items in order by comparing the current item with the previous item. If they are in order, move to the next item (or stop if the end is reached). If they are out of order, swap them and move to the previous item. If there is no previous item, move to the next item.
Generalization (I am a kind of ...)
stable sort, in-place sort.
See also insertion sort, bidirectional bubble sort.
Note: Complexity is O(n2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning.
This can be seen as an insertion sort that only keeps track of the current item. After having moved an item backward into place, it "walks" forward, checking the order of items as it goes, until it reaches the next item is out of place, which is beyond where progress left off.
This can be seen as a bidirectional bubble sort that intelligently reverses direction, instead of making complete passes.
Dick Grune, the inventor, calls this "the simplest sort algorithm."
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 19 October 2007.
HTML page formatted Fri Oct 19 14:20:39 2007.
Cite this as:
Paul E. Black, "gnome sort", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 19 October 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/gnomeSort.html
