Download and view my resume (PDF)

Saturday, September 12, 2009

Insertionsort in perl

Insertion sort is significantly slower than the other sorts, but I think I could improve this by doing an O(log n) insert, whereas here I have a linear insert.

#!perl


use strict;

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

#Generate a large number of random integers
$list_size = 10000;
$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;
@numbers = @{insertionsort(\@numbers)};
#print "\n\n@numbers";
print "INSERTIONSORT sorted $list_size integers between 1 and $max_num in " . (time - $start_time) . " seconds\n";

#Insertion sort is how humans often sort a deck of cards
#Start with a stack of unsorted numbers, pop each number in turn
#And insert it into a second sorted stack at the proper place
sub insertionsort {
my ($numbers, @sorted, $found);
($numbers) = @_;
my @sorted = ();

for(my $i = 0; $i <= $#{$numbers}; $i++) {
$found = 0;
for(my $j = 0; $j <= $#sorted; $j++) {
if( $numbers->[$i] < $sorted[$j] ) {
splice @sorted, $j, 0, $numbers->[$i];
$found = 1;
last;
}
}
unless ($found) { push @sorted, $numbers->[$i]; }
}

return \@sorted;
}

No comments:

Post a Comment