Gnome sort (nicknamed stupid sort) is a variation of the insertion sort sorting algorithm that does not use nested loops. Gnome sort was known for a long time and used without naming it explicitly. It was then popularized 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(n2) but tends towards O(n) if the list is initially almost sorted.Almost sorted means that each item in the list is not far from its proper position (not farther than some small constant distance).
Dick Grune described the sorting method with the following story:
Pseudocode Here is pseudocode for the gnome sort using a zero-based array:
procedure gnomeSort(a[]): pos := 1 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
References
External links
Gnome sort