Gnome sort
From Wikipedia, the free encyclopedia
Gnome sort is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. The name comes from the supposed behavior of the Dutch garden gnome in sorting a line of flowerpots[citation needed] and is described on Dick Grune's Gnome sort page
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 backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.
It is conceptually simple, requiring no nested loops. The running time is O(n²), but in practice the algorithm can run as fast as Insertion sort.
[edit] Description
Here is pseudocode for the sort:
function gnomeSort(a[0..size-1]) {
i := 1
j := 2
while i < size
if a[i-1] >= a[i] # for ascending sort, reverse the comparison to <=
i := j
j := j + 1
else
swap a[i-1] and a[i]
i := i - 1
if i = 0
i := 1
}
Here is the same code in Python:
def gnomeSort(a) :
i = 1
j = 2
while i < len(a) :
if a[i - 1] >= a[i] :
i = j
j += 1
else :
a[i], a[i - 1] = a[i - 1], a[i]
i-=1
if i == 0 :
i = 1
Example:
If we wanted to sort an array with elements [4] [2] [7] [3], here is what would happen with each iteration of the while loop:
[4] [2] [7] [3] (initial state. i is 1 and j is 2.)
[4] [2] [7] [3] (did nothing, but now i is 2 and j is 3.)
[4] [7] [2] [3] (swapped a[i - 1] and a[i]. now i is 1 and j is still 3.)
[7] [4] [2] [3] (swapped a[i - 1] and a[i]. now i is 1 and j is still 3.)
[7] [4] [2] [3] (did nothing, but now i is 3 and j is 4.)
[7] [4] [3] [2] (swapped a[i - 1] and a[i]. now i is 4 and j is 5.)
at this point the loop ends because i isn't < 4.
The algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. It takes advantage of the fact that performing a swap can only introduce a new out-of-order adjacent pair right before the two swapped elements, and so checks this position immediately after performing such a swap.
[edit] External links
|
||||||||||||||||||||||||||||
