GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages
Algorithm::Networksort::Best(3) User Contributed Perl Documentation Algorithm::Networksort::Best(3)

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

    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";
    }

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:

'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.

'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.

'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.

'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.

'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.

'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.

'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.

'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).

'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.

'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.

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

'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.

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

'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.

'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.

'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>.

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().

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.

Doug Hoyte <https://github.com/hoytech> pointed out Sherenaz Waleed Al-Haj Baddar's paper.

Morwenn <https://github.com/Morwenn> found for me the SAT and SENSO papers, contributed 23-input and 24-input sorting networks, and caught documentation errors.

  • 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>.

John M. Gamble may be found at jgamble@cpan.org
2022-04-08 perl v5.32.1

Search for    or go to Top of page |  Section 3 |  Main Index

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with ManDoc.