Download and view my resume (PDF)

Wednesday, August 24, 2011

Gnomesort in perl


I also implemented gnomesort, which simulates the presumed method of sorting for common garden gnomes, widely understood to prefer their flower pots in ascending order, from smallest to biggest. To sort them, starting on the left, the gnome compares each pot to the one on its left. If the one on the left is bigger, he swaps the two pots and steps left. Otherwise he steps right. He is done when he steps past the rightmost pot.

So gnomesort is similar to an in-place insertion sort, where the pots up to a certain point are sorted, and as you move right and get to new pots, you insert them into the leftish sorted region by comparing them in descending order until you get to the right spot.

#!perl


use strict;

my ($list_size, $max_num, @numbers, $start_time);

#Generate a large number of random integers
$list_size = 1000;
$max_num = 1000;
@numbers = ();
for(1..$list_size) {
push(@numbers, int(rand($max_num)));
}

#Print out the number array, then sort it, then print it out again in sorted order
#print "\n\n@numbers";
$start_time = time;
gnomesort(\@numbers);
#print "\n\n@numbers";
print "GNOMESORT sorted $list_size numbers between 1 and $max_num in " . (time - $start_time) . " seconds\n";

#In gnomesort, you compare an item to its neighbor, perhaps swap those items, and then step left or right
#Any item is compared to its left neighbor
#If they are out of order, swap them, and step left
#If they are in order, step right
#The first item is considered sorted by definition, so step right
#You are complete when you step off the right end of the array
sub gnomesort {
my( $numbers ) = @_;

my $i = 0;
my $a = $numbers->[$i-1];
my $b = $numbers->[$i];

while( defined($b) ) {
if( $i == 0 ) {
$i++;
} elsif( $b < $a ) { swap( $i, $i - 1, $numbers ); $i--; } else { $i++; } $a = $numbers->[$i-1];
$b = $numbers->[$i];
}
}

#A swap operation takes a list reference and exchanges the values at the indicated indices
#The swap operation allows quicksort to work in one list
sub swap {
my( $index1, $index2, $anyarray ) = @_;
$_ = $anyarray->[$index1];
$anyarray->[$index1] = $anyarray->[$index2];
$anyarray->[$index2] = $_;
}

No comments:

Post a Comment