Kyle Brandt

Introduction:
O’Reilly’s Mastering Algorithms with Perl is written for programmers who are already quite familiar with Perl. I thought it might help myself and maybe others to walk through the code for selection sort that is on Page 120 because the code isn’t the clearest Perl. My analysis is not meant to explain selection sort because the book does that. Rather, it is to explain the Perl code.

The Code:

#!/usr/bin/perl 

use strict;
use warnings;

sub selection_sort {
    my $array = shift;

    my $i;      # The starting index of a minimum-finding scan.
    my $j;      # The running index of a minimum-finding scan.

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

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

        # Swap if needed.
        @$array[ $m, $i ] = @$array[ $i, $m ] unless $m == $i;
    }
}

my @array = (1, 7, 2, 8, 2, 5, 20);
selection_sort(\@array);
print "@array\n";

The only change I made to the code from the example is to change lt to < on line 18 so the comparison is numerical and not by ascii value.

Analysis:
Line 27 passes a reference to the @array array to the selection_sort subroutine. This makes it so the array is changed in place and a copy of the array does not have to be made.

Line 7 makes the variable $array , which is local to the function selection_sort, a reference to the array in line 26. ’shift’ removes the first argument to the function from the @_ array. The @_ is the default variable within a subroutine so it can be omitted. The line could have been written as $array = shift(@_); .

Line 12 uses a c-style for loop (Please forgive the messed up syntax highlighting). In Perl for and foreach do the same thing. However, a for or foreach loop is context sensitive depending on what comes after the for/foreach keyword. So Perl programmers use for when they are writing a c-style loop. The c-style loop is used for array indexing here. The first statement, $i = 0; initializes the index variable. The second statement, $i < $#$array; is the exit condition as in a while loop. The third statement $i++ increments by one each loop. In the second statement, $#$array, means ‘the index of the last element of the array that the reference $array points to’. Since it is less than instead of less than or equal to, and it is the last index of the array, not the number of items in the array, the loop will stop before the last element of the array.

Line 14 is again using references, so $array->[ $m ] returns the value of the index $m in array that $array points to.

Line 16, like 12, uses the c-style loop. This time the exit condition (the second statement in the loop header) is $j < @$array . This dereferences the array that $array points to, and evaluates in scalar context which returns the number of items in the array. So this also could have been written as $j <= $#$array .

Line 17 and 18 are like a standard if statement but it is written backwards. This is known as postfix syntax, a trailing conditional, or a statement-modifying if. Note, this is written as one line — there is no semi-colon.

Line 22 also uses the trailing conditional, this time it is ‘unless’. This line uses array slices to swap the items. The slice [ $m, $i ] selects two items, the item at index $m and index $i . It does not select a range like the python array[0:2] . In Perl you use the range operator .. instead of : . And again @$array deferences the array, you will often see this written as @{$array} .

Conclusion
I hope this helps someone else who is reading this book, thanks to everyone in #perl on irc.freenode.com for the help.