Download and view my resume (PDF)

Friday, September 11, 2009

Quicksort in perl

This is quicksort implemented in perl. This implementation run on a Macbook Pro 2.4GHz Dual Core machine sorts 100,000 random integers between 1 and 1000 in about three seconds. That is reasonably quick, but compares approximately to mergesort, and performance degrades considerably if the integers have lower cardinality (a smaller overall numerical range).

#!perl

use strict;

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

#Generate a large number of random integers
$list_size = 100000;
$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 "@numbers\n";
$start_time = time;
quicksort(0, $#numbers, \@numbers);
#print "@numbers\n";
print "QUICKSORT sorted $list_size random integers between 1 and $max_num in " . (time - $start_time) . " seconds.\n";

#Quicksort works by dividing the list into two parts around an arbitrary pivot number
#We arbitrarily choose the first number in the list to be the pivot
#Then we simply recurse over the bottom and top parts of the list
#The recursion stops when the list of the length ("right minus left") is 1
sub quicksort {
my( $left, $right, $quicknums ) = @_;

if( $right > $left ) {
my $pivotNewIndex = partition($left, $right, $left, $quicknums);
quicksort($left, $pivotNewIndex -1, $quicknums);
quicksort($pivotNewIndex + 1, $right, $quicknums);
}
}

#To partition a list around a pivot index, we put each element above or below the pivot
#The result is a list which is partially sorted, in that the list as a whole has a high and low part
#We do this by first moving the pivot value safely to the end of the list
#Then we compare each item with the list to the pivot, moving lower values to the left in the array
#Finally we put the pivot back into place between the two parts of the list and return its new index
sub partition {
my( $left, $right, $pivotIndex, $partnums ) = @_;
my ($pivotValue, $storeIndex);

$pivotValue = $partnums->[$pivotIndex];
swap($pivotIndex, $right, $partnums);
$storeIndex = $left;

for( my $i = $left; $i <= $right; $i++ ) {
if( $partnums->[$i] < $pivotValue ) {
swap($i, $storeIndex, $partnums);
$storeIndex++;
}
}
swap($storeIndex, $right, $partnums);
return $storeIndex;
}

#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