Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Release history of Algorithm-Networksort
branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
eg
lib/Algorithm
t
Build.PL
Changes
LICENSE
MANIFEST
META.json
META.yml
Makefile.PL
README

README

Algorithm::Networksort version 1.30
===================================

    "I've got to sort this out. ... There must be a list somewhere
    of the ones these bastards were nicking, and I wish I had it.  I
    would make it even money that the name of the murderer is on it.
    Would you?"

    "No."

    "Anything to be contrary. Why not?"

    "You haven't done enough sorting, Mr. Cramer."
        The Golden Spiders, by Rex Stout (1953, ch. 13)

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 used in software with a compiler
that can take advantage of parallelism.  However, the arrangement of
the comparisons is fixed according to the number of elements to be
sorted, so a network cannot be used as a generic sort like
quicksort.

There are several algorithms to generate sorting networks.  This
module has four of them:  Bose and Nelson's, Hibbard's, Batcher's
Merge Exchange, and Batcher's Bitonic (thanks to Doug Hoyte, who
contributed the bitonic code).  It also has networks that
were found to be superior in comparison count to those generated
automatically by these algorithms; and a sorting network equivalent
of Bubble sort (for comparison and teaching purposes only -- please
do not use for any real production).

There is a flexible formatting function that will allow you to
print out your network in many ways (see documentation).  There
is also a graphical output function that will return the network
in an encapsulated postscript, SVG, or text form.

INSTALLATION

The usual way.  Unpack the archive:
	gzip -d Algorithm-Networksort-1.30.tar.gz
	tar xvf Algorithm-Networksort-1.30.tar

Go into the resulting directory, and type:
	perl Build.PL
	Build

Run the tests:
	Build test

Install the module:
	Build install


MORE ON TESTING

With the addition of 'best' networks for sizes 18 and 22, the testing
time went from 'lengthy' to 'intolerable for unsuspecting CPAN testers'.
Consequently, the sorting tests now have an upper limit of 10 for
normal testing. This size goes up to 17 if the environment variable
AUTHOR_TESTING is set (and the size 12 and up 'best' networks are also
tested).

If you want to have the full testing experience, I've provided a switch
that will automatically do all this for you. Run the tests with

	Build test --Testlong

and the full suite will run (and depending on your machine, you may have
time to go out and get lunch). If you want to run only a single test file,
then the Module-Build switch '--test_files' can select that file for you:

	Build test --test_files=t/best13.t --Testlong

Note that the '--Testlong' switch comes last.


DEPENDENCIES

This module requires no other modules and libraries.  If you want
to view the SVG output, good starting points would be Inkscape, Firefox
(version 3.6 or better), and Apache's Batik project for Java.
Postscript viewing is easily accomplished with GNU's ghostview program.

COPYRIGHT AND LICENSE

Copyright (C) 2012 John M. Gamble. All rights reserved. This program is
free software; you can redistribute it and/or modify it under the same
terms as Perl itself.
Something went wrong with that request. Please try again.