Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
Algorithm::NetworksortUser Contributed Perl DocumentaAlgorithm::Networksort(3)

NAME
       Algorithm::Networksort -	Create Sorting Networks.

SYNOPSIS
	   use 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();

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

   Exported Functions
       For 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(), or nwsrt().

	   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_title

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

   Methods
       new()

	   $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 $inputs items.	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 the algorithm key 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 what nwsrt_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, see	network().

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

       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	last sort() 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."

   Methods For Printing
       The 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
       (see formatted()).  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 (see
       formatted()). 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 the	formats() 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	using inputs_base().

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

	   print $nw->formatted();

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

	   $nw->input_base([1..$inputs]);
	   print $nw->formatted();

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

	   $nw->formats([ "SWAP(%d, %d);\n" ]);
	   print $nw->formatted();

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

	   $nw->input_base([1..$inputs]);
	   $nw->formats([ "SWAP(%d, %d);\n" ]);
	   print $nw->formatted();

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

	   $nw->formats([ "if (v[%d] < v[%d]) then\n",
		       "    exchange(v,	%d, %d)\nend if\n" ]);
	   print $nw->formatted();

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

	   $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 in network().

       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.

   Methods For Graphing
       graph_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--o

       colorsettings()

       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 for graph_svg() and graph_eps():

       SVG measurements	are in pixels.

       'hz_margin
	  Default value: 18.  The horizontal spacing between the edges of the
	  graphic and the sorting network.

       'hz_sep
	  Default value: 12.  The spacing separating the horizontal lines (the
	  input	lines).

       'indent'
	  Default value: 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'
	  Default value: 2.  Radii of the circles used to end the comparator
	  and input lines.

       'stroke_width
	  Default value: 2.  Width of the lines	used to	define comparators and
	  input	lines.

       'vt_margin
	  Default value: 21.  The vertical spacing between the edges of	the
	  graphic and the sorting network.

       'vt_sep
	  Default value: 12.  The spacing separating the vertical lines	(the
	  comparators).

       Options for graph_text():

       'inputbegin'
	  Default value: "o-".	The starting characters	for the	input line.

       'inputline'
	  Default value: "---".	 The characters	that make up an	input line.

       'inputcompline'
	  Default value: "-|-".	 The characters	that make up an	input line
	  that has a comparator	crossing over it.

       'inputend'
	  Default value: "-o\n".  The characters that make up the end of an
	  input	line.

       'compbegin'
	  Default value: "-^-".	 The characters	that make up an	input line
	  with the starting point of a comparator.

       'compend'
	  Default value: "-v-".	 The characters	that make up an	input line
	  with the end point of	a comparator.

       'gapbegin'
	  Default value: "  " (two spaces).  The characters that start the gap
	  between the input lines.

       'gapcompline'
	  Default value: " | " (space vertical bar space).  The	characters
	  that make up the gap with a comparator passing through.

       'gapnone'
	  Default value: "  " (three spaces).  The characters that make	up the
	  space	between	the input lines.

       'gapend'
	  Default value: "  \n"	(two spaces and	a newline).  The characters
	  that end the gap between the input lines.

ACKNOWLEDGMENTS
       Doug 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 the statistics() method.

       Morwenn <https://github.com/Morwenn> found documentation	errors and
       networks	that went into Algorithm::Networksort::Best.

SEE ALSO
   Bose	and Nelson's algorithm.
       o  Bose and Nelson, "A Sorting Problem",	Journal	of the ACM, Vol. 9,
	  1962,	pp. 282-296.

       o  Joseph Celko,	"Bose-Nelson Sort", Doctor Dobb's Journal, September
	  1985.

       o  Frederick Hegeman, "Sorting Networks", The C/C++ User's Journal,
	  February 1993.

       o  Joe Celko, Joe Celko's SQL For Smarties (third edition).
	  Implementing Bose-Nelson sorting network in SQL.

	  This material	isn't in either	the second or fourth edition of	the
	  book.

       o  Joe Celko, Joe Celko's Thinking in Sets: Auxiliary, Temporal,	and
	  Virtual Tables in SQL.

	  The sorting network material removed from the	third edition of SQL
	  For Smarties seems to	have been moved	to this	book.

   Hibbard's algorithm.
       o  T. N.	Hibbard, "A Simple Sorting Algorithm", Journal of the ACM Vol.
	  10, 1963, pp.	142-50.

   Batcher's Merge Exchange algorithm.
       o  Code for Kenneth Batcher's Merge Exchange algorithm was derived from
	  Knuth's The Art of Computer Programming, Vol.	3, section 5.2.2.

   Batcher's Bitonic algorithm
       o  Kenneth 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.

       o  Dr. 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>

       o  T. H.	Cormen,	E. E. Leiserson, R. L. Rivest, Introduction to
	  Algorithms, first edition, McGraw-Hill, 1990,	section	28.3.

       o  T. H.	Cormen,	E. E. Leiserson, R. L. Rivest, C. Stein, Introduction
	  to Algorithms, 2nd edition, McGraw-Hill, 2001, section 27.3.

   Algorithm discussion
       o  Donald E. Knuth, The Art of Computer Programming, Vol. 3: (2nd ed.)
	  Sorting and Searching, Addison Wesley	Longman	Publishing Co.,	Inc.,
	  Redwood City,	CA, 1998.

       o  Kenneth Batcher's web	site (<http://www.cs.kent.edu/~batcher/>)
	  lists	his publications, including his	paper listed above.

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

perl 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>

home | help