NAME

Algorithm::Networksort::Best - Optimized Sorting Networks.

SYNOPSIS

use Algorithm::Networksort;
use Algorithm::Networksort::Best qw(:all);

my $inputs = 9;

#
# First find if any networks exist for the input size.
#
my @nwkeys = nw_best_names($inputs);

#
# For each sorting network, show the comparators.
#
for my $name (@nwkeys)
{
    my $nw = nwsrt_best(name => $name);

    #
    # Print the list, and print the graph of the list.
    #
    print $nw->title(), "\n", $nw->formatted(), "\n\n";
    print $nw->graph_text(), "\n\n";
}

DESCRIPTION

For some inputs, sorting networks have been discovered that are more efficient than those generated by rote algorithms. The "Best" module allows you to use those networks instead.

There is no guarantee that it will return the best network for all cases. Usually "best" means that the module will return a lower number of comparators for the number of inputs than the algorithms in Algorithm::Networksort will return. Some will simply have a lower number of comparators, others may have a smaller depth but an equal or greater number of comparators.

The current networks are:

9-Input Networks

'floyd09'

A 9-input network of depth 9 discovered by R. W. Floyd. Of interest also because it is using what are essentially three-way comparators split into three sets of two-way comparators.

'senso09'

A 9-input network of depth 8 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

10-Input Networks

'waksman10'

A 10-input network of depth 9 found by A. Waksman.

'senso10'

A 10-input network of depth 8 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

11-Input Networks

'shapirogreen11'

An 11-input network of depth 9 found by G. Shapiro and M. W. Green.

'senso11'

A 11-input network of depth 10 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

12-Input Networks

'shapirogreen12'

A 12-input network of depth 9 found by G. Shapiro and M. W. Green.

'senso12'

A 12-input network of depth 9 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

13-Input Networks

'end13'

A 13-input network of depth 10 generated by the END algorithm, by Hugues Juill�.

'senso13'

A 13-input network of depth 12 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

14-Input Networks

'green14'

A 14-input network of depth 10 created by taking the 16-input network of M. W. Green and removing inputs 15 and 16.

'senso14'

A 14-input network of depth 11 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

15-Input Networks

'green15'

A 15-input network of depth 10 created by taking the 16-input network of M. W. Green and removing the 16th input.

'senso15'

A 15-input network of depth 10 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

16-Input Networks

'green16'

A 16-input network of depth 10 found by M. W. Green.

'senso16'

A 16-input network of depth 10 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

'vanvoorhis16'

From the book Designing Sorting Networks (see "Non-algorithmic discoveries" below).

17-Input Networks

'senso17'

A 17-input network of depth 17 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

'sat17'

17-input network of depth 10 found by M. Codish, L. Cruz-Filipe, T. Ehlers, M. M�ller, P. Schneider-Kamp.

18-Input Networks

'alhajbaddar18'

18-input network of depth 11 found by Sherenaz Waleed Al-Haj Baddar.

'senso18'

A 18-input network of depth 15 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

19-Input Networks

'senso19'

A 19-input network of depth 15 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

20-Input Networks

'sat20'

20-input network of depth 11 found by M. Codish, L. Cruz-Filipe, T. Ehlers, M. M�ller, P. Schneider-Kamp.

'senso20'

A 20-input network of depth 14 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

21-Input Networks

'senso21'

A 21-input network of depth 20 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

22-Input Networks

'alhajbaddar22'

22-input network of depth 12 found by Sherenaz Waleed Al-Haj Baddar.

'senso22'

A 22-input network of depth 15 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

23-Input Networks

'morwenn23'

A 23-input network of depth 18 found by Morwenn, by taking the 24-input network and removing the final input.

'senso23'

A 23-input network of depth 22 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.

24-Input Networks

'morwenn24'

A 24-input network of depth 18 found by Morwenn https://github.com/Morwenn/cpp-sort/wiki/Original-research#sorting-networks-23-and-24.

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 nwsrt_best(), nw_best_names(), and nw_best_title().

Functions

nwsrt_best

Return the Algorithm::Networksort object, given a key name. Also takes an optional title to override the default.

$nw = nwsrt_best(name => 'floyd09', title => "Compare depth to Bose-Nelson");

nw_best_names

Return the list of keys for sorting networks of a giving input size.

@names = nw_best_names(13);

Each name key is a valid option for the name argument of nwsrt_best().

An unlikely example:

my $inputs = 12;

for my $name (nwsrt_best_names($inputs))
{
	my $nw = nwsrt_best(name => $name);
	print $nw->title(), "\n", $nw, "\n";
}

To get the list of all available names (regardless of input size), simply call the function with no argument:

my @names = nwsrt_best_names();

nw_best_title

Return a descriptive title for the network, given a name key.

$title = nw_best_title($key);

These are the titles for the available networks. 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.

ACKNOWLEDGMENTS

Doug Hoyte pointed out Sherenaz Waleed Al-Haj Baddar's paper.

Morwenn found for me the SAT and SENSO papers, contributed 23-input and 24-input sorting networks, and caught documentation errors.

SEE ALSO

Non-algorithmic discoveries

• The networks by Floyd, Green, Shapiro, and Waksman are in Donald E. Knuth's The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998.

• The Evolving Non-Determinism (END) algorithm by Hugues Juill� has found more efficient sorting networks: http://www.cs.brandeis.edu/~hugues/sorting_networks.html.

• The 18 and 22 input networks found by Sherenaz Waleed Al-Haj Baddar are described in her dissertation "Finding Better Sorting Networks" at http://etd.ohiolink.edu/view.cgi?acc_num=kent1239814529.

• The 16 input network found by David C. Van Voorhis is described in chapter 5 of Designing Sorting Networks, by Sherenaz W. Al-Haj Baddar and Kenneth E. Batcher.

• The Symmetry and Evolution based Network Sort Optimization (SENSO) found more networks for inputs of 9 through 23.

• Morwenn's 23 and 24-input networks are described at https://github.com/Morwenn/cpp-sort/wiki/Original-research#sorting-networks-23-and-24.

• Ian Parberry, "A computer assisted optimal depth lower bound for sorting networks with nine inputs", http://www.eng.unt.edu/ian/pubs/snverify.pdf.

AUTHOR

John M. Gamble may be found at jgamble@cpan.org

cpanm Algorithm::Networksort

perl -MCPAN -e shell
install Algorithm::Networksort