Exported Functions

nwsrt()

Simple function to save the programmer from the agony of typing "Algorithm::Networksort->new()":

    use Algorithm::Networksort;

    my $nw = nwsrt(inputs => 13, algorithm => 'bitonic');

nwsrt_algorithms()

Return a sorted list algorithm choices. Each one is a valid key for the algorithm argument of Algorithm::Networksort->new(), or nwsrt().

    use Algorithm::Networksort;

    my @alg_keys = nwsrt_algorithms();

    print "The available keys for the algorithm argument are (",
            join(", ", @alg_keys), ")\n";

Or, for an even less likely example:

    my $inputs = 6;

    for my $al (nwsrt_algorithms())
    {
        my $nw = nwsrt(inputs => $inputs, algorithm => $al);
        print $nw->title(), "\n", $nw, "\n";
    }

nwsrt_title

Return a descriptive title for an algorithm, given the algorithm's key name.

    $title = nwsrt_title($key);

These are the titles for the available algorithms. By themselves, they provide a readable list of choices for an interactive program. They are not to be confused with a sorting network's title, which may be set by the programmer.

Methods

    $nw1 = Algorithm::Networksort->new(inputs => $inputs,
                                       algorithm => 'batcher');

    $nw2 = Algorithm::Networksort->new(inputs => $inputs,
                                       algorithm => 'oddevenmerge');

Returns an object that contains, among other things, a list of comparators that can sort $inputs items. The algorithm for generating the list may be chosen, but by default the sorting network is generated by the Bose-Nelson algorithm.

Arguments to new()

'inputs'

The number of inputs of the sorting network.

'algorithm'

The choices for the algorithm key are

'comparators'

The list of comparators provided by the user instead of by an algorithm.

comparators()

The comparators in their 'raw' form, as generated by its algorithm.

For the comparators re-ordered in such a way as to take advantage of parallelism, see network().

network()

Returns the comparators re-ordered from the 'raw' form, providing a parallelized version of the comparator list; e.g., the best order possible to prevent stalling in a CPU's pipeline.

This is the form used when printing the sorting network using formats().

algorithm_name()

Return the full text name of the algorithm, given its key name.

sort()

Sort an array using the network. This is meant for testing purposes only - looping around an array of comparators in order to sort an array in an interpreted language is not the most efficient mechanism for using a sorting network.

This function uses the "<=>" operator for comparisons.

    my @digits = (1, 8, 3, 0, 4, 7, 2, 5, 9, 6);
    my $nw = Algorithm::Networksort->new(
                        inputs => (scalar @digits),
                        algorithm => 'hibbard');
    $nw->sort(\@digits);
    print join(", ", @digits);

statistics()

Return statistics on the last sort() call. Currently only "swaps", a count of the number of exchanges, is returned.

    my(@d, %nw_stats);
    my @digits = (1, 8, 3, 0, 4, 7, 2, 5, 9, 6);
    my $inputs = scalar @digits;
    my $nw_batcher = Algorithm::Networksort->new(inputs => $inputs, algorithm => 'batcher');
    my $nw_bn = Algorithm::Networksort->new(inputs => $inputs, algorithm => 'bosenelson');

    #
    # List will wind up sorted, so copy it for our first test run.
    #
    @d = @digits;
    $nw_batcher->sort(\@d);
    %nw_stats = $nw_batcher->statistics();
    print "The Batcher Merge-Exchange network took ",
        $nw_stats{swaps}, " exchanges to sort the array."

    @d = @digits;
    $nw_bn->sort(\@d);
    %nw_stats = $nw_bn->statistics();
    print "The Bose-Nelson network took ",
        $nw_stats{swaps}, " exchanges to sort the array."

Methods For Printing

    my $nw = nwsrt(inputs => 8, algorithm => 'bosenelson');
    print $nw . "\n";

Will result in the output

    [[0,1], [2,3], [4,5], [6,7],
    [0,2], [1,3], [4,6], [5,7],
    [1,2], [5,6], [0,4], [3,7],
    [1,5], [2,6],
    [1,4], [3,6],
    [2,4], [3,5],
    [3,4]]

If you had shifted the array index by one using index_base():

    my $nw = nwsrt(inputs => 8, algorithm => 'bosenelson');
    $nw->index_base([1 .. 8]);
    print $nw . "\n";

This would have resulted in the output

    [[1,2], [3,4], [5,6], [7,8],
    [1,3], [2,4], [5,7], [6,8],
    [2,3], [6,7], [1,5], [4,8],
    [2,6], [3,7],
    [2,5], [4,7],
    [3,5], [4,6],
    [4,5]]

For a wider variety of outputs, use "formats()" and "index_base()" as described below.

formats()

An array reference of format strings, for use in formatted printing (see formatted()). You may use as many sprintf-style formats as you like to form your output.

    $nw->formats([ "swap(%d, %d) ", "if ($card[%d] < $card[%d]);\n" ]);

index_base()

The values to use to reference array indices in formatted printing (see formatted()). By default, array indices are zero-based. To use a different index base (most commonly, one-based array indexing), use this method.

    $nw->index_base([1 .. $inputs]);

formatted()

    $string = $nw->formatted();

Returns a formatted string that represents the list of comparators.

If no formats have been provided via the formats() method, the default format will be used: an array of arrays as represented in Perl.

Likewise, the network sorting pairs are zero-based. If you want the pairs written out for some sequence other than 0, 1, 2, ... then you can provide that using inputs_base().

Example 0: you want a string in the default format.

    print $nw->formatted();

Example 1: you want the output to look like the default format, but one-based instead of zero-based.

    $nw->index_base([1..$inputs]);
    print $nw->formatted();

Example 2: you want a simple list of SWAP macros.

    $nw->formats([ "SWAP(%d, %d);\n" ]);
    print $nw->formatted();

Example 3: as with example 2, but the SWAP values need to be one-based instead of zero-based.

    $nw->index_base([1..$inputs]);
    $nw->formats([ "SWAP(%d, %d);\n" ]);
    print $nw->formatted();

Example 4: you want a series of comparison and swap statements.

    $nw->formats([ "if (v[%d] < v[%d]) then\n",
                "    exchange(v, %d, %d)\nend if\n" ]);
    print $nw->formatted();

Example 5: you want the default format to use letters, not numbers.

    $nw->index_base( [('a'..'z')[0..$inputs]] );
    $nw->formats([ "[%s,%s]," ]);      # Note that we're using the string flag.

    my $string = '[' . $nw->formatted();
    substr($string, -1, 1) = ']';    # Overwrite the trailing comma.

    print $string, "\n";

group()

Takes the comparator list and returns a list of comparator lists, each sub-list representing a group of comparators that can be operate without interfering with each other, depending on what is needed for interference-free grouping.

There is one option available, 'grouping', that will produce a grouping that represents parallel operations of comparators. Its values may be:

'graph'

Group the comparators as parallel as possible for graphing.

'parallel'

Arrange the sequence in parallel so that it has a minimum depth. This, after flattening the lists into a single list again, is what is used to produce the sequence in network().

number

Arrange the comparators every number count. This is for simple printing of the comparators, without any grouping for graphing or maximum parallelization.

The chances that you will need to use this function are slim, but the following code snippet may represent an example:

    my $nw = Algorithm::Networksort->new(inputs => 8, algorithm => 'batcher');

    print "There are ", $nw->length(),
        " comparators in this network, grouped into\n",
        $nw->depth(), " parallel operations.\n\n";

    print $nw, "\n";

    my @grouped_network = $nw->group(grouping=>'graph');
    print "\nThis will be graphed in ", scalar @grouped_network,
        " columns.\n";

This will produce:

    There are 19 comparators in this network, grouped into 6 parallel operations.

    [[0,4], [1,5], [2,6], [3,7]]
    [[0,2], [1,3], [4,6], [5,7]]
    [[2,4], [3,5], [0,1], [6,7]]
    [[2,3], [4,5]]
    [[1,4], [3,6]]
    [[1,2], [3,4], [5,6]]

    This will be graphed in 11 columns.

Methods For Graphing

Returns a string that graphs out the network's comparators. The format will be encapsulated postscript.

    my $nw = nwsrt(inputs = 4, algorithm => 'bitonic');

    print $nw->graph_eps();

graph_svg()

Returns a string that creates a Knuth diagram of a network.

    $nw = nwsrt(inputs => 4, algorithm => 'bitonic');
    $diagram = $nw->graph_svg();    # Using default attributes.

The string will consist of SVG drawing tags enclosed by <svg> and </svg> tags.

The attributes of the diagram can be changed via colorsettings() and graphsettings().

    $nw = nwsrt_best(name => 'floyd09');   # See Algorithm::Networksort::Best

    $nw->colorsettings(compbegin => '#04c', compend => '#00c');
    $diagram = $nw->graph_svg();

graph_text()

Returns a string that graphs out the network's comparators in plain text.

    my $nw = Algorithm::Networksort(inputs = 4, algorithm => 'bitonic');

    print $nw->graph_text();

This will produce

    o--^-----^--^--o
       |     |  |   
    o--v--^--|--v--o
          |  |      
    o--^--v--|--^--o
       |     |  |   
    o--v-----v--v--o

colorsettings()

Sets the colors of the graph parts, currently for Postscript and SVG output only.

The parts are named.

    my %old_colors = $nw->colorsettings(compbegin => "#cc0044", compend => "#cc4400");

You may use web colors <https://en.wikipedia.org/wiki/Web_colors> names in place of the hex triplet if creating an SVG document (Postscript will not understand it, however). The shorthand hexadecimal form (using only three digits) is also valid, as it will be converted into the standard six digit form before writing out the diagram.

'inputbegin'

Opening of input line.

'inputline'

The input line.

'inputend'

Closing of the input line.

'compbegin'

Opening of the comparator.

'compline'

The comparator line.

'compend'

Closing of the comparator line.

'foreground'

Default color for the graph as a whole.

'background'

Color of the background.

All parts not named are reset to 'undef' (which means calling "colorsettings()" with no arguments resets everything), and will be colored with the 'foreground' color. The foreground color itself has a default value of '#000000' (black). The one exception is 'background', which has no default color at all.

graphsettings()

Alter diagram properties such as line width or margin size.

    #
    # Set hz_margin, saving its old value for later.
    #
    my %old_gset = $nw->graphsettings(hz_margin => 12);

Options

SVG measurements are in pixels.

'hz_margin'

Default value: 18. The horizontal spacing between the edges of the graphic and the sorting network.

'hz_sep'

Default value: 12. The spacing separating the horizontal lines (the input lines).

'vt_margin'

Default value: 21. The vertical spacing between the edges of the graphic and the sorting network.

'vt_sep'

Default value: 12. The spacing separating the vertical lines (the comparators).

'indent'

Default value: 9. The indention between the start of the input lines and the placement of the first comparator. The same value spaces the placement of the final comparator and the end of the input lines.

'compline'

Default value: 2. Width of the lines used to draw comparators.

'compradius'

Default value: 2. Radii of the circles used on either end of the comparator lines.

'inputline'

Default value: 2. Width of the lines used to draw input lines.

'inputradius'

Default value: 2. Radii of the circles used on either end of the input lines.

Options for graph_text():

'inputbegin'

Default value: "o-". The starting characters for the input line.

'inputline'

Default value: "---". The characters that make up an input line.

'inputcompline'

Default value: "-|-". The characters that make up an input line that has a comparator crossing over it.

'inputend'

Default value: "-o\n". The characters that make up the end of an input line.

'compbegin'

Default value: "-^-". The characters that make up an input line with the starting point of a comparator.

'compend'

Default value: "-v-". The characters that make up an input line with the end point of a comparator.

'gapbegin'

Default value: " " (two spaces). The characters that start the gap between the input lines.

'gapcompline'

Default value: " | " (space vertical bar space). The characters that make up the gap with a comparator passing through.

'gapnone'

Default value: " " (three spaces). The characters that make up the space between the input lines.

'gapend'

Default value: " \n" (two spaces and a newline). The characters that end the gap between the input lines.

textsettings()

Alter the text settings for the ascii-art characters.

    #
    # Set different beginning and ending characters.
    #
    my %old_gset = $nw->textsettings(
            inputbegin => '---', gapbegin => '   ',
            inputend => '---\n', gapend => '   \n'
        );

Options

'inputbegin'

Default value: "o-". The starting characters for the input line.

'inputline'

Default value: "---". The characters that make up an input line.

'inputcompline'

Default value: "-|-". The characters that make up an input line that has a comparator crossing over it.

'inputend'

Default value: "-o\n". The characters that make up the end of an input line.

'compbegin'

Default value: "-^-". The characters that make up an input line with the starting point of a comparator.

'compend'

Default value: "-v-". The characters that make up an input line with the end point of a comparator.

'gapbegin'

Default value: " " (two spaces). The characters that start the gap between the input lines.

'gapcompline'

Default value: " | " (space vertical bar space). The characters that make up the gap with a comparator passing through.

'gapnone'

Default value: " " (three spaces). The characters that make up the space between the input lines.

'gapend'

Default value: " \n" (two spaces and a newline). The characters that end the gap between the input lines.

Bose and Nelson's algorithm.

• Bose and Nelson, "A Sorting Problem", Journal of the ACM, Vol. 9, 1962, pp. 282-296.
• Joseph Celko, "Bose-Nelson Sort", Doctor Dobb's Journal, September 1985.
• Frederick Hegeman, "Sorting Networks", The C/C++ User's Journal, February 1993.
• Joe Celko, Joe Celko's SQL For Smarties (third edition). Implementing Bose-Nelson sorting network in SQL.

  This material isn't in either the second or fourth edition of the book.

• Joe Celko, Joe Celko's Thinking in Sets: Auxiliary, Temporal, and Virtual Tables in SQL.

  The sorting network material removed from the third edition of SQL For Smarties seems to have been moved to this book.

Hibbard's algorithm.

•

T. N. Hibbard, "A Simple Sorting Algorithm", Journal of the ACM Vol. 10, 1963, pp. 142-50.

Batcher's Merge Exchange algorithm.

•

Code for Kenneth Batcher's Merge Exchange algorithm was derived from Knuth's The Art of Computer Programming, Vol. 3, section 5.2.2.

Batcher's Bitonic algorithm

• Kenneth Batcher, "Sorting Networks and their Applications", Proc. of the AFIPS Spring Joint Computing Conf., Vol. 32, 1968, pp. 307-3114. A PDF of this article may be found at <http://www.cs.kent.edu/~batcher/sort.pdf>.

  The paper discusses both the Odd-Even Merge algorithm and the Bitonic algorithm.

• Dr. Hans Werner Lang has written a detailed discussion of the bitonic sort algorithm here: <http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm>
• T. H. Cormen, E. E. Leiserson, R. L. Rivest, Introduction to Algorithms, first edition, McGraw-Hill, 1990, section 28.3.
• T. H. Cormen, E. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd edition, McGraw-Hill, 2001, section 27.3.

Algorithm discussion

• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998.
• Sherenaz W. Al-Haj Baddar and Kenneth E. Batcher, Designing Sorting Networks: A New Paradigm, Springer-Verlag, 2011
• Kenneth Batcher's web site (<http://www.cs.kent.edu/~batcher/>) lists his publications, including his paper listed above.