This may be the fastest, this may be the slowest, I don’t care. What matters to me is this is a very small sort algorithm, which can be easily crammed and can be used whenever I want to use a sort logic.

This algorithm is originally proposed by Hamid Sarbazi-Azad under the name Stupid Sort, and was first developed by Dick Grune under the name Gnome Sort.
From Grune’s page
Gnome Sort is based on the technique used by the standard Dutch Garden Gnome. 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.

procedure gnomeSort(a[])
pos := 1
while pos < length(a)
if (a[pos] >= a[pos-1])
pos := pos + 1
else
swap a[pos] and a[pos-1]
if (pos > 1)
pos := pos – 1
else
pos := pos + 1
end if
end if
end while
end procedure
Advertisements