I don't have a lot to say, but this is my little bit.

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).


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);
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