#!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;

}

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.

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment