Gnome sort
|
|
Gnome sort is a sort 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. It is conceptually simple, requiring no nested loops. The running time is O(n2), and in practice the algorithm has been reported to run slightly slower than bubble sort, although this depends on the details of the architecture and the implementation.
| Contents |
Description
Here is pseudocode for the sort:
function gnomeSort(a[1..size]) {
i := 2
while i ≤ size
if i = 1 or a[i-1] ≤ a[i]
i := i + 1
else
swap a[i-1] and a[i]
i := i - 1
}
Effectively, the algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. If this place were searched for naively, the result would be the O(n3) stupid sort. Instead, 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.
Implementations
C++
int gnomeSort(int array[], int size)
{
int i = 1;
int swapNum;
while (i<size)
{
if (i==0 || array[i-1]<= array[i])
i++; //Increment i
else
{
//SWAP NUMBERS
swapNum = array[i-1];
array[i-1] = array[i];
array[i] = swapNum;
i--; //Decrement i
}
}
}
Perl
sub gnome_sort(@)
{
my @a = @_;
my $i=0;
while ($i < @a) {
if ($i==0 or $a[$i-1] <= $a[$i]) {
$i++;
} else {
($a[$i-1],$a[$i]) = ($a[$i],$a[$i-1]);
$i--;
}
}
return @a;
}
Python
def gnome_sort(L):
L = L[:]
i = 0
while i < len(L):
if i == 0 or L[i-1] <= L[i]:
i += 1
else:
L[i], L[i-1] = L[i-1], L[i]
i -= 1
return L
FORTRAN 77
SUBROUTINE gnome_sort(A, LEN)
INTEGER A, LEN, I, TEMP
DIMENSION A(LEN)
I = 2
WHILE (I .LE. LEN) DO
IF ((I .EQ. 1) .OR. (A(I-1) .LE. A(I))) THEN
I = I + 1
ELSE
TEMP = A(I)
A(I) = A(I-1)
A(I-1) = TEMP
I = I - 1
END IF
END WHILE
END
External link
- Gnome sort (http://www.cs.vu.nl/~dick/gnomesort.html).