Sorting Networks

Number of inputs: (maximum 32).

Algorithm choices:

View the network via SVG *.

View the network using text characters if you can't view SVG.

Display the encapsulated postscript code.

Display the SVG tags.

Create a set of SWAP macros.

Algorithm::Networksort is a perl module that implements Bose-Nelson, Hibbard, and Batcher's algorithms for network sorts. A network sort, also known as an oblivious sort, is a set of comparators. Each comparator exchanges its inputs if the inputs are out of order. Since each comparator has no knowledge of what any other comparator has done, the arrangement of the comparators alone is what guarantees the inputs will be sorted.

In real-world applications, the comparators may be circuits on a chip, or a set of compare-and-swap macros in a C program. It helps to graph the comparators as lines that cross the input lines to give a feel for the layout, which is one of the things that this demonstration page can do.

Algorithm Choices

The different methods of generating networks came from entirely different intentions. Bose and Nelson's algorithm is recursive, easy to code, and produces moderately parallel sets of comparators. Hibbard's algorithm generates comparators on an as-needed basis. It is a fast iterative algorithm, but does not produce very parallel sets of comparators. Batcher's algorithm is a side-effect of his Merge-Exchange sorting algorithm. Merge-Exchange is, like quicksort or heapsort, an algorithm that can handle arrays of any size, but it was noted that it produced the same set of comparisons for each individual array size. Therefore, if you simply kept track of the comparisons and their order, you would have a set of comparators for a network. The result is a highly parallel set of comparators.

The "best" choice returns a network that was created not by a rote algorithm, but by a search for the best known arrangement of comparators. Currently more efficient networks (that is, those with fewer comparators) that do better than the known algorithms have been discovered for inputs of nine through sixteen. For inputs of eight or less, the rote algorithms produce the best known results, and no "best" networks have been discovered for inputs greater than sixteen yet. If you try to select "best" with inputs outside the range of nine through sixteen, you will be using Bose-Nelson.

SVG (Scalable Vector Graphics) is an XML based graphics standard that produces images quickly and compactly. Web sites that discuss SVG are and the SVG Foundation. If you are using Internet Explorer to view the network, you will need to install the SVG plugin from Adobe. Opera users can view it natively if they are using version 8 (found at Firefox support of SVG is not ready yet, although there are some rumblings in that area as the Mozilla people can tell you in their FAQ .

Made with jEdit
Powered by Perl

Valid HTML 4.01!