Class: | Sorting algorithm |
Data: | Array |
Time: | O(n2) |
Best-Time: | O(n) |
Average-Time: | O(n2) |
Space: | O(1) |
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] [5]
Dick Grune described the sorting method with the following story:
Here is pseudocode for the gnome sort using a zero-based array:
procedure gnomeSort(a[]): pos := 0 while pos < length(a): if (pos
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 |