# FreeBSD Manual Pages

Algorithm::NetworksortUser Contributed Perl DocumentaAlgorithm::Networksort(3)NAMEAlgorithm::Networksort - Create Sorting Networks.SYNOPSISuse Algorithm::Networksort; my $inputs = 4; my $algorithm = "bosenelson"; # # Generate the sorting network (a list of comparators). # my $nw = Algorithm::Networksort->new(inputs =>$inputs algorithm => $algorithm); # # Print the comparator list using the default format, # and print a graph of the list. # print $nw->formatted(), "\n"; print $nw->graph_text(), "\n"; # # Set up a pretty SVG image. # $nw->graphsettings(vt_margin => 8, vt_sep => 13, hz_sep=>15); $nw->colorsettings(foreground => "#206068", background => "#c8c8c8"); print $nw->graph_svg();DESCRIPTIONThis 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 if used in software with a compiler that can take advantage of parallelism. Unfortunately a sorting network cannot be used for generic run-time sorting like quicksort, since the arrangement of the comparisons is fixed according to the number of elements to be sorted. This 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 sorting networks in either encapsulated postscript (EPS), scalar vector graphics (SVG), or in "ascii art" format.ExportedFunctionsFor convenience's sake, there are three exported functions to save typing and inconvenient look-ups.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(), ornwsrt(). 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_titleReturn a descriptive title for the network, given an 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.Methodsnew()$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$inputsitems. The algorithm for generating the list may be chosen, but by default the sorting network is generated by the Bose-Nelson algorithm. The choices for thealgorithmkey are 'bosenelson' Use the Bose-Nelson algorithm to generate the network. This is the most commonly implemented algorithm, recursive and simple to code. 'hibbard' Use Hibbard's algorithm. This iterative algorithm was developed after the Bose-Nelson algorithm was published, and produces a different network "... for generating the comparisons one by one in the order in which they are needed for sorting," according to his article (see below). 'batcher' Use Batcher's Merge Exchange algorithm. Merge Exchange is a real sort, in that in its usual form (for example, as described in Knuth) it can handle a variety of inputs. But while sorting it always generates an identical set of comparison pairs per array size, which lends itself to sorting networks. 'bitonic' Use Batcher's bitonic algorithm. A bitonic sequence is a sequence that monotonically increases and then monotonically decreases. The bitonic sort algorithm works by recursively splitting sequences into bitonic sequences using so-called "half-cleaners". These bitonic sequences are then merged into a fully sorted sequence. Bitonic sort is a very efficient sort and is especially suited for implementations that can exploit network parallelism. 'oddevenmerge' Use Batcher's Odd-Even Merge algorithm. This sort works in a similar way to a regular merge sort, except that in the merge phase the sorted halves are merged by comparing even elements separately from odd elements. This algorithm creates very efficient networks in both comparators and stages. 'bubble' Use a naive bubble-sort/insertion-sort algorithm. Since this algorithm produces more comparison pairs than the other algorithms, it is only useful for illustrative purposes. 'oddeventrans' Use a naive odd-even transposition sort. This is a primitive sort closely related to bubble sort except it is more parallel. Because other algorithms are more efficient, this sort is included for illustrative purposes. 'balanced' This network is described in the 1983 paper "The Balanced Sorting Network" by M. Dowd, Y. Perl, M Saks, and L. Rudolph. It is not a particularly efficient sort but it has some interesting properties due to the fact that it is constructed as a series of successive identical sub-blocks, somewhat like with 'oddeventrans'. 'none' Do not generate a set of comparators. Instead, take the set from an outside source, using the "comparators" option. # # Test our own 5-input network. # @cmptr = ([1,2], [0,2], [0,1], [3,4], [0,3], [1,4], [2,4], [1,3], [2,3]); $nw = Algorithm::Networksort->new(inputs => 5, algorithm => 'none', comparators => [@cmptr]); Internally, this is whatnwsrt_best()of Algorithm::Networksort::Best uses.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, seenetwork().network()Returns the comparators re-ordered from the 'raw' order, to provide a parallelized version of the comparator list; the best order possible to prevent stalling in a CPU's pipeline. This is the form used when printing the sorting network usingformats().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 lastsort()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."MethodsForPrintingThe network object by default prints itself in a grouped format; that is my $nw = nwsrt(inputs => 4, algorithm => 'bosenelson'); print $nw; Will result in the output [[0,1], [2,3], [0,2], [1,3], [1,2]]formats()An array reference of format strings, for use in formatted printing (seeformatted()). 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 (seeformatted()). 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 theformats()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 usinginputs_base().Example0:youwantastringinthedefaultformat.print $nw->formatted();Example1:youwanttheoutputtolooklikethedefaultformat,butone-basedinsteadofzero-based.$nw->input_base([1..$inputs]); print $nw->formatted();Example2:youwantasimplelistofSWAPmacros.$nw->formats([ "SWAP(%d, %d);\n" ]); print $nw->formatted();Example3:aswithexample2,buttheSWAPvaluesneedtobeone-basedinsteadofzero-based.$nw->input_base([1..$inputs]); $nw->formats([ "SWAP(%d, %d);\n" ]); print $nw->formatted();Example4:youwantaseriesofcomparisonandswapstatements.$nw->formats([ "if (v[%d] < v[%d]) then\n", " exchange(v, %d, %d)\nend if\n" ]); print $nw->formatted();Example5:youwantthedefaultformattouseletters,notnumbers.$nw->input_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 comnparators 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 innetwork(). 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.MethodsForGraphinggraph_eps()Returns a string that graphs out the network's comparators. The format will be encapsulated postscript. my $nw = Algorithm::Networksort(inputs = 4, algorithm => 'bitonic'); print $nw->graph_eps();graph_svg()Returns a string that graphs out the network's comparators. $nw = Algorithm::Networksort(inputs => 4, algorithm => 'bitonic'); $svg = $nw->graph_svg(); The output will use the default colors and sizes, and will be enclosed between <svg> and </svg> tags. An example of using the output in an HTML setting: $nw = nwsrt_best(name => 'floyd09'); # See Algorithm::Networksort::Best $nw->colorsettings(compbegin => '#04c', compend => '#40c'); $svg = $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--ocolorsettings()Sets the colors of the graph parts, currently for SVG output only. The parts are named. my %old_colors = $nw->colorsettings(inputbegin => "#c04", inputend => "#c40"); '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. Currently unimplemented in SVG. All parts not named are reset to 'undef', and will be colored with the default 'foreground' color. The foreground color itself has a default value of 'black'. The one exception is the 'background' color, which has no default color at all.graphsettings()Alter the graphing settings, be it pixel measurements or ascii-art characters. # # Set hz_margin, saving its old value for later. # my %old_gset = $nw->graphsettings(hz_margin => 12); Options forgraph_svg()andgraph_eps(): SVG measurements are in pixels. 'hz_marginDefaultvalue:18.The horizontal spacing between the edges of the graphic and the sorting network. 'hz_sepDefaultvalue:12.The spacing separating the horizontal lines (the input lines). 'indent'Defaultvalue: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. 'radius'Defaultvalue:2.Radii of the circles used to end the comparator and input lines. 'stroke_widthDefaultvalue:2.Width of the lines used to define comparators and input lines. 'vt_marginDefaultvalue:21.The vertical spacing between the edges of the graphic and the sorting network. 'vt_sepDefaultvalue:12.The spacing separating the vertical lines (the comparators). Options forgraph_text(): 'inputbegin'Defaultvalue:"o-".The starting characters for the input line. 'inputline'Defaultvalue:"---".The characters that make up an input line. 'inputcompline'Defaultvalue:"-|-".The characters that make up an input line that has a comparator crossing over it. 'inputend'Defaultvalue:"-o\n".The characters that make up the end of an input line. 'compbegin'Defaultvalue:"-^-".The characters that make up an input line with the starting point of a comparator. 'compend'Defaultvalue:"-v-".The characters that make up an input line with the end point of a comparator. 'gapbegin'Defaultvalue:""(twospaces).The characters that start the gap between the input lines. 'gapcompline'Defaultvalue:"|"(spaceverticalbarspace).The characters that make up the gap with a comparator passing through. 'gapnone'Defaultvalue:""(threespaces).The characters that make up the space between the input lines. 'gapend'Defaultvalue:"\n"(twospacesandanewline).The characters that end the gap between the input lines.ACKNOWLEDGMENTSDoug Hoyte <https://github.com/hoytech> provided the code for the bitonic, odd-even merge, odd-even transposition, balanced, and bubble sort algorithms, and the idea for what became thestatistics()method. Morwenn <https://github.com/Morwenn> found documentation errors and networks that went into Algorithm::Networksort::Best.SEE ALSOBoseandNelson'salgorithm.oBose and Nelson, "A Sorting Problem", Journal of the ACM, Vol. 9, 1962, pp. 282-296.oJoseph Celko, "Bose-Nelson Sort", Doctor Dobb's Journal, September 1985.oFrederick Hegeman, "Sorting Networks", The C/C++ User's Journal, February 1993.oJoe Celko,JoeCelko'sSQLForSmarties(third edition). Implementing Bose-Nelson sorting network in SQL. This material isn't in either the second or fourth edition of the book.oJoe Celko,JoeCelko'sThinkinginSets:Auxiliary,Temporal,andVirtualTablesinSQL. The sorting network material removed from the third edition ofSQLForSmartiesseems to have been moved to this book.Hibbard'salgorithm.oT. N. Hibbard, "A Simple Sorting Algorithm", Journal of the ACM Vol. 10, 1963, pp. 142-50.Batcher'sMergeExchangealgorithm.oCode for Kenneth Batcher's Merge Exchange algorithm was derived from Knuth's The Art of Computer Programming, Vol. 3, section 5.2.2.Batcher'sBitonicalgorithmoKenneth 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.oDr. 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>oT. H. Cormen, E. E. Leiserson, R. L. Rivest, Introduction to Algorithms, first edition, McGraw-Hill, 1990, section 28.3.oT. H. Cormen, E. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd edition, McGraw-Hill, 2001, section 27.3.AlgorithmdiscussionoDonald E. Knuth, The Art of Computer Programming, Vol. 3: (2nd ed.) Sorting and Searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998.oKenneth Batcher's web site (<http://www.cs.kent.edu/~batcher/>) lists his publications, including his paper listed above.AUTHORJohn M. Gamble may be found atjgamble@cpan.orgperl v5.24.1 2017-07-02 Algorithm::Networksort(3)

NAME | SYNOPSIS | DESCRIPTION | ACKNOWLEDGMENTS | SEE ALSO | AUTHOR

Want to link to this manual page? Use this URL:

<https://www.freebsd.org/cgi/man.cgi?query=Algorithm::Networksort&sektion=3&manpath=FreeBSD+12.0-RELEASE+and+Ports>