 NAME
 SYNOPSIS
 DESCRIPTION
 9Input Networks
 10Input Networks
 11Input Networks
 12Input Networks
 13Input Networks
 14Input Networks
 15Input Networks
 16Input Networks
 17Input Networks
 18Input Networks
 19Input Networks
 20Input Networks
 21Input Networks
 22Input Networks
 23Input Networks
 24Input Networks
 Export
 Functions
 ACKNOWLEDGMENTS
 SEE ALSO
 AUTHOR
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:
9Input Networks
 'floyd09'

A 9input network of depth 9 discovered by R. W. Floyd. Of interest also because it is using what are essentially threeway comparators split into three sets of twoway comparators.
 'senso09'

A 9input network of depth 8 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
10Input Networks
 'waksman10'

A 10input network of depth 9 found by A. Waksman.
 'senso10'

A 10input network of depth 8 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
11Input Networks
 'shapirogreen11'

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

A 11input network of depth 10 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
12Input Networks
 'shapirogreen12'

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

A 12input network of depth 9 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
13Input Networks
 'end13'

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

A 13input network of depth 12 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
14Input Networks
 'green14'

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

A 14input network of depth 11 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
15Input Networks
 'green15'

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

A 15input network of depth 10 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
16Input Networks
 'green16'

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

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

From the book Designing Sorting Networks (see "Nonalgorithmic discoveries" below).
17Input Networks
 'senso17'

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

17input network of depth 10 found by M. Codish, L. CruzFilipe, T. Ehlers, M. M�ller, P. SchneiderKamp.
18Input Networks
 'alhajbaddar18'

18input network of depth 11 found by Sherenaz Waleed AlHaj Baddar.
 'senso18'

A 18input network of depth 15 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
19Input Networks
 'senso19'

A 19input network of depth 15 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
20Input Networks
 'sat20'

20input network of depth 11 found by M. Codish, L. CruzFilipe, T. Ehlers, M. M�ller, P. SchneiderKamp.
 'senso20'

A 20input network of depth 14 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
21Input Networks
 'senso21'

A 21input network of depth 20 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
22Input Networks
 'alhajbaddar22'

22input network of depth 12 found by Sherenaz Waleed AlHaj Baddar.
 'senso22'

A 22input network of depth 15 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
23Input Networks
 'morwenn23'

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

A 23input network of depth 22 found using the SENSO program by V. K. Valsalam and R. Miikkulaainen.
24Input Networks
 'morwenn24'

A 24input network of depth 18 found by Morwenn https://github.com/Morwenn/cppsort/wiki/Originalresearch#sortingnetworks23and24.
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 BoseNelson");
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 AlHaj Baddar's paper.
Morwenn found for me the SAT and SENSO papers, contributed 23input and 24input sorting networks, and caught documentation errors.
SEE ALSO
Nonalgorithmic 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 NonDeterminism (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 AlHaj 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. AlHaj 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 24input networks are described at https://github.com/Morwenn/cppsort/wiki/Originalresearch#sortingnetworks23and24.
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