Perl Bucket Sort

#!/usr/bin/perl

use constant BUCKET_SIZE => 10;

sub bucket_sort {
    my ($array, $min, $max) = @_;
    my $N = @$array or return;

    my $range    = $max - $min;
    my $N_BUCKET = $N / BUCKET_SIZE;
    my @bucket;

    # Create the buckets.
    for ( my $i = 0; $i < $N_BUCKET; $i++ ) {
        $bucket[ $i ] = [ ];
    }

    # Fill the buckets.
    for ( my $i = 0; $i < $N; $i++ ) {
        my $bucket = $N_BUCKET * (($array->[ $i ] - $min)/$range);
        push @{ $bucket[ $bucket ] }, $array->[ $i ];
    }


    # Sort inside the buckets.
    for ( my $i = 0; $i < $N_BUCKET; $i++ ) {
        insertion_sort( $bucket[ $i ] );
    }

    # Concatenate the buckets.

    @{ $array } = map { @{ $_ } } @bucket;
}

sub insertion_sort {
    my $array = shift;

    my $i; # The initial index for the minimum element.
    my $j; # The running index for the minimum-finding scan.

    for ( $i = 0; $i < $#$array; $i++ ) {
        # The final index for the minimum element.
        my $m = $i;
        # The minimum value.
        my $x = $array->[ $m ];

        for ( $j = $i + 1; $j < @$array; $j++ ) {
             # Update minimum.
            ( $m, $x ) = ( $j, $array->[ $j ] )
              if $array->[ $j ] lt $x;
        }

# The double-splice simply moves the $m-th element to be
# the $i-th element.  Note: splice is O(N), not O(1).
# As far as the time complexity of the algorithm is concerned
# it makes no difference whether we do the block movement
# using the preceding loop or using splice().  Still, splice()
# is faster than moving the block element by element.
        splice @$array, $i, 0, splice @$array, $m, 1 if $m > $i;
    }
}

@array = qw(1 8 7 4 0 9 8 3 7 1 6 8 1 1 8 7 6 4 4 8 9 4 0 3 9 3 2 3 9);

bucket_sort(\@array, 0, 9);

print "@array\n";

Related Tutorials

• « Previous page
• Next page »