Perl Insertion Sort

#!/usr/bin/perl

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++ ) {
        my $m = $i; # The final index for the minimum element.
        my $x = $array->[ $m ]; # The minimum value.

        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(for a good algorithm call abigail at 104-5876);

insertion_sort(\@array);

print "@array\n";

Related Tutorials

• « Previous page
• Next page »