(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 input list is nearly in order.
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 out-of-place item, which is beyond where progress left off.
Timothy Rolfe finds it "convenient to think of [gnome sort] as 'a variant of insertion sort that hides the logic in a single loop.'" This can be seen by commenting a minor rewrite, after Rolfe, of Dick Grune's implementation:
void gnomesort(int n, int ar[]) {
for (int i = 0; i < n; ) {
if (i == 0 || ar[i-1] <= ar[i]) {
// Outer loop functionality --- scan to larger index
i++;
} else {
// Inner loop functionality --- move to smaller index
int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;
}
}
}
This can also be seen as a bidirectional bubble sort that intelligently reverses direction, instead of making complete passes.
Dick Grune calls this "the simplest sort algorithm."
Author: PEB
Hamid Sarbazi-Azad, Stupid Sort: A new sorting algorithm, Department of Computing Science Newsletter, University of Glasgow, 599:4, 2 October 2000.
Historical Note
Originally called "stupid sort". Dick Grune wrote, "The earliest evidence [of inventing gnome sort] I can find is of March 22, 2003, but I'm pretty sure I thought of the idea much earlier."
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 6 October 2010.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "gnome sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 6 October 2010. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/gnomeSort.html