Algorithm Implementation/Sorting/Gnome sort
Jump to navigation
Jump to search
C
[edit | edit source]void gnome_sort(int *array, int size){
int i, tmp;
for(i=1; i<size; ){
if(array[i-1] <= array[i])
++i;
else{
tmp = array[i];
array[i] = array[i-1];
array[i-1] = tmp;
--i;
if(i == 0)
i = 1;
}
}
}
C++
[edit | edit source]#include <algorithm> // for std::swap
void gnomeSort( int *array, int size )
{
for ( int i = 1; i < size; ) {
if ( array[i-1] <= array[i] ) {
++i;
}
else {
std::swap( array[i-1], array[i] );
--i;
if ( i == 0 ) {
i = 1;
}
}
}
}
C++ using bidirectional iterators
[edit | edit source]#include <algorithm> // for std::iter_swap
template <typename Iterator>
void gnome_sort(Iterator begin, Iterator end)
{
Iterator current = begin;
Iterator before_current;
while (current != end)
{
if (current == begin || *before_current <= *current)
{
++current;
}
else
{
std::iter_swap(before_current, current);
--current;
}
before_current = current;
--before_current;
}
}
Optimized C++ using iterators
[edit | edit source]#include <algorithm> // for std::iter_swap
#include <iterator> // for std::advance
template <typename Iterator>
void gnome_sort(Iterator begin, Iterator end)
{
Iterator current = begin;
Iterator before_current;
size_t step = 1;
while (current != end)
{
if (current == begin || *before_current <= *current)
{
std::advance(current, step); // possible leap optimization
step = 1;
}
else
{
std::iter_swap(before_current, current);
--current;
++step;
}
before_current = current;
--before_current;
}
}
The optimized version makes the "gnome" (represented by the 'current' iterator here) leap back to the right i.e. to the place where it needed to swap the flower pots on its farthest reached position so far. This also avoids redundant comparisons. On average the optimization results in cutting the time by one/third on a modern x86 machine. (A wise gnome sort? :). However, the optimization works best if the iterators are random access iterators. Otherwise the algorithm works almost like the non-optimized version - it still avoids redundant comparisons though.
C#
[edit | edit source]void GnomeSort( int[] array )
{
for ( int i = 1, temp_value; i < array.Length; )
{
if ( array[i-1] <= array[i] )
i += 1;
else
{
temp_value = array[i-1];
array[i-1] = array[i];
array[i] = temp_value;
i -= 1;
if ( i == 0 )
i = 1;
}
}
}
SUBROUTINE gnome_sort(LIST, LENGTH)
INTEGER LIST, LENGTH, I, TEMP
DIMENSION LIST(LENGTH)
I = 2
DO WHILE (I .LE. LENGTH)
IF ((I .EQ. 1) .OR. (LIST(I-1) .LE. LIST(I))) THEN
I = I + 1
ELSE
TEMP = LIST(I)
LIST(I) = LIST(I-1)
LIST(I-1) = TEMP
I = I - 1
IF (I .EQ. 1) THEN
I = 2
END IF
END IF
END DO
END
Java
[edit | edit source]public class GnomeSort {
static void gnomeSort( int[] theArray ) {
for ( int index = 1; index < theArray.length; ) {
if ( theArray[index - 1] <= theArray[index] ) {
++index;
} else {
int tempVal = theArray[index];
theArray[index] = theArray[index - 1];
theArray[index - 1] = tempVal;
--index;
if ( index == 0 ) {
index = 1;
}
}
}
}
function gnomeSort(sortMe) {
i=0;
while (i < sortMe.length) {
if (i==0||sortMe[i-1] <= sortMe[i]) {
i++;
} else {
tmp=sortMe[i];
sortMe[i]=sortMe[i-1];
sortMe[--i]=tmp;
}
}
}
This sorts an scope-accessible index:objectype (IndexName) passed by variable name, sorting by MemberName, which should be a numeric member of objecttype.
method Gnomesort(string IndexName, string MemberName)
{
variable int i = 1
while ${i} <= ${${IndexName}.Used}
{
if ( ${i} == 1 ) || ${${IndexName}[${Math.Calc[${i}-1]}].${MemberName}} <= ${${IndexName}[${i}].${MemberName}}
{
i:Inc
}
else
{
${IndexName}:Swap[${i}, ${Math.Calc[${i}-1]}]
i:Dec
}
}
}
Perl
[edit | edit source]sub gnome_sort(@) {
my @list = @_;
my $size = scalar(@list);
my $right = 1;
while ( $right < $size ) {
my $left = $right - 1;
if ( $list[$left] <= $list[$right] ) {
$right++;
}
else {
@list[ $left, $right ] = @list[ $right, $left ];
$right-- if $right > 1;
}
}
return @list;
}
Phix
[edit | edit source]function gnomeSort(sequence s)
integer i = 1, j = 2
while i<length(s) do
if s[i]<=s[i+1] then
i = j
j += 1
else
{s[i],s[i+1]} = {s[i+1],s[i]}
i -= 1
if i = 0 then
i = j
j += 1
end if
end if
end while
return s
end function
PHP
[edit | edit source]<?php
function gnome_sort($list)
{
for ($i = 1; $i < count($list);)
{
if ($list[$i-1] <= $list[$i]) {$i++;}
else
{
$temp = $list[$i];
$list[$i] = $list[$i-1];
$list[$i-1] = $temp;
$i--;
if ($i == 0) {$i = 1;}
}
}
return $list;
}
?>
def gnomeSort(items):
i = 0
n = len(items)
while i < n:
if i and items[i] < items[i-1]:
items[i], items[i-1] = items[i-1], items[i]
i -= 1
else:
i += 1
return items
def teleportingGnomeSort(items):
i = j = 0
n = len(items)
while i < n:
if i and items[i] < items[i-1]:
items[i], items[i-1] = items[i-1], items[i]
i -= 1
else:
if i < j: # teleport!
i = j
j = i = i+1
return items
Ruby
[edit | edit source]module GnomeSort
def self.sort(keys)
sort!(keys.clone)
end
def self.sort!(keys)
i, j = 1, 2
while i < keys.size
if keys[i-1] <= keys[i]
i, j = j, j+1
else
keys[i-1], keys[i] = keys[i], keys[i-1]
i -= 1 if i > 1
end
end
keys
end
end