Algorithm::Networksort - Create inline comparisons for sorting.

EXPORT

Functions
AUTHOR
SEE ALSO

Bose and Nelson's algorithm.
Hibbard's algorithm.
Batcher's Merge Exchange algorithm.
Non-algorithmic discoveries
Algorithm discussion

NAME

Algorithm::Networksort - Create inline comparisons for sorting.

SYNOPSIS

  use Algorithm::Networksort qw(:all);

  my $inputs = 4;

  #
  # Generate the network (a list of comparators).
  #
  my @network = nw_comparators($inputs);

  #
  # Print the list, and print the graph of the list.
  #
  print nw_format(\@network, $inputs), "\n";
  print nw_graph(\@network, $inputs), "\n";

PREREQUISITES

Perl 5.6 or later. This is the version of perl under which this module was developed.

DESCRIPTION

This module will create sorting networks, a sequence of comparisons that do not depend upon the results of prior comparisons.

Since the sequences and their order never change, they can be very useful if deployed in hardware, or used in software with a compiler that can take advantage of parallelism. However, the arrangement of the comparisons is fixed according to the number of elements to be sorted, so a network cannot be used for generic run-time sorting like quicksort.

The module's main purpose is to create compare-and-swap macros (or functions, or templates) that one may insert into source code. It may also be used to create images of the networks in either encapsulated postscript (EPS), scalar vector graphics (SVG), or in ``ascii art'' format.

EXPORT

None by default. There is only one available export tag, ':all', which exports the functions to create and use sorting networks. The functions are nw_comparator(), nw_format(), nw_graph(), nw_group(), and nw_sort().

Functions

nw_comparator

    @network = nw_comparator($inputs);

    @network1 = nw_comparator($inputs, algorithm => $alg);

Returns a list of comparators that can sort $inputs items. The algorithm for generating the list may be chosen, but by default the network is generated by the Bose-Nelson algorithm. The different methods will produce different networks in general, although in some cases the differences will be in the arrangement of the comparators, not in their number.

The choices for algorithm are

'bosenelson'

Use the Bose-Nelson algorithm to generate the network. This is the most commonly implemented algorithm.

'hibbard'

Use Hibbard's algorithm. Hibbard's algorithm makes use of bit placement in integers. Currently, plain old 32-bit integers are used. If you specify 'hibbard' with more than 32 elements the module will fall back to Bose-Nelson.

'batcher'

Use Batcher's Merge Exchange algorithm. Batcher's algorithm also makes use of bit placement, and like Hibbard's algorithm it will fall back to Bose-Nelson if more than 32 elements are specified.

'best'

For some inputs, networks have been discovered that are more efficient than those generated by rote algorithms. When 'best' is specified one of these are returned instead. The term ``best'' does not actually guarantee the best network for all cases. It simply means that at the time of this version of the module, the network returned has the lowest number of comparators for the number of inputs. Considerations of parallelism, or of other networks with an equally low comparator count but different arrangement are ignored.

Currently more efficient networks have been discoverd for inputs of nine through sixteen. If you choose 'best' outside of this range the module will fall back to Bose-Nelson.

nw_format

    $string = nw_format(\@network, $format1, $format2, \@index_base);

Returns a formatted string that represents the list of comparators. There are two sprintf-style format strings, which lets you separate the comparison and exchange portions if you want. The second format string is optional.

The first format string may also be ignored, in which case the default format will be used: an array of arrays as represented in perl.

The network sorting pairs are zero-based. If you want the pairs written out for some other sequence other than 0, 1, 2, ... then you can provide that in an array reference.

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

    print nw_format(\@network);

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

    print nw_format(\@network,
                undef,
                undef,
                [1..$inputs]);

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

    print nw_format(\@network, "SWAP(%d, %d);\n");

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

    print nw_format(\@network,
                "SWAP(%d, %d);\n",
                undef,
                [1..$inputs]);

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

    print nw_format(\@network,
                "if (v[%d] < v[%d]) then\n",
                "    exchange(v, %d, %d)\nend if\n");

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

    my @alphabase = ('a'..chr($inputs));

    my $string = '[' .
            nw_format(\@network,
                "[%s,%s],",      # Note that we're using the string flag.
                undef,
                \@alphabase);

substr($string, -1, 1) = ']'; # Overwrite the trailing comma. print $string;

nw_graph

Returns a string that graphs out the comparators in a network. The format may be encapsulated postscript (graph=>'eps'), scalar vector graphics (graph=>'svg'), or the default plain text (graph=>'text' or none). The 'text' and 'eps' options produce output that is self-contained. The 'svg' option produces output between <svg> and </svg> tags, which needs to be combined with XML code in order to be viewed.

    my $inputs = 4;
    my @network = nw_comparators($inputs);
    $netgraph = nw_graph(\@network, $inputs, graph=>'svg');

    print "<?xml version=\"1.0\" standalone=\"no\"?>\n",
        "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 20001102//EN\"\n",
        "         \"http://www.w3.org/TR/2000/CR-SVG-20001102/DTD/"; .
        "svg-20001102.dtd\">\n",
        $netgraph;

nw_group

This is a function called by nw_graph(). The function takes the comparator list and returns a list of comparator lists, each sub-list representing a group of comparators that can be printed in a single column.

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

    my $inputs = 4;
    my @network = nw_comparators($inputs);
    print nw_format(\@network);
    my @grouped_network = nw_group(\@network, $inputs);

    print "There are ", scalar @grouped_network,
          " columns in the printed network\n\n";

    foreach my $group (@grouped_network)
    {
        print nw_format($group), "\n";
    }

This will produce:

    There are 4 columns in the printed network

    [[0,1],[2,3]]
    [[0,2]]
    [[1,3]]
    [[1,2]]

nw_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 @network = nw_comparators(scalar @digits, algorithm => 'best');
    nw_sort(\@network, \@digits);
    print join(", ", @digits);

AUTHOR

John M. Gamble, <jgamble@ripco.com>