Sorting network

Sorting network

A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sort the values by outputting the smaller value to one wire, and a larger value to the other. The main difference between sorting networks and comparison sorting algorithms is that the sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. Despite the simplicity of the model, sorting network theory is surprisingly deep and complex.

Introduction

A sorting network consists of two things, comparators and wires. Each wire carries with it a value, and each comparator takes two wires as input and output. When two values enter a comparator, the comparator emits the lower value from the top wire, and the higher value from the bottom wire. A network of wires and comparators that will correctly sort all possible inputs into ascending order is called a sorting network.

The full operation of a simple sorting network is shown below. It is easy to see why this sorting network will correctly sort the inputs; note that the first four comparators will "sink" the largest value to the bottom and "float" the smallest value to the top. The final comparator simply sorts out the middle two wires.

Insertion and Selection networks

We can easily construct a network of any size recursively using the principles of insertion and selection. Assuming we have a sorting network of size n, we can construct a network of size n+1 by "inserting" an additional number into the already sorted subnet (using the principle behind insertion sort). We can also accomplish the same thing by first "selecting" the lowest value from the inputs and then sort the remaining values recursively (using the principle behind bubble sort).

The structure of these two sorting networks are very similar. A construction of the two different variants that collapses together comparators that can be performed simultaneously shows that, in fact, they are identical.

Efficient networks

The insertion network has a large depth of O("n") making it impractical. There are simple networks which achieve depth O((log "n")2) (hence size O("n" (log "n")2)), such as Batcher's Odd-even mergesort, bitonic sort, and Shell sort. These networks are often used in practice.

Zero-one principle

While it is easy to prove the validity of some sorting networks (like the insertion/bubble sorter), it is not always so easy. There are n! permutations of numbers in an n-wire network, and to test all of them would take a significant amount of time, especially on larger networks. However, because of the so-called Zero-one principle, far fewer trials are in fact needed to test the validity of a sorting network.

The Zero-one principle states that a sorting network is valid if it can sort all 2^n sequences of 0s and 1s. This drastically cuts down on the number of tests needed to ascertain the validity of a network, as well is of great use in creating many constructions of sorting networks.

The proof is a special case of Bouricius's Theorem, proved by W. G. Bouricius in 1954.

Optimal sorting

The efficiency of a sorting network can be measured by its total size (the number of comparators used), or by its depth (the maximum number of comparators along any path from an input to an output). The asymptotically best sorting network, discovered by Ajtai, Komlós, and Szemerédi, achieves depth O(log "n") and size O("n" log "n") for "n" inputs, which is asymptotically optimal. A simplified version of the AKS network was described by Paterson. While an important theoretical discovery, the AKS network has little or no practical application because of the large linear constants hidden by the Big-O notation. These are partly due to a construction of an expander graph. Finding sorting networks with size "cn" log "n" for small "c" remains a fundamental open problem.

References

* O. Angel, A.E. Holroyd, D. Romik, B. Virag, " [http://arxiv.org/abs/math/0609538 Random Sorting Networks] ", Adv. in Math., 215(2):839–868, 2007.
* K.E. Batcher, " [http://www.cs.kent.edu/~batcher/sort.ps Sorting networks and their applications] ", Proceedings of the AFIPS Spring Joint Computer Conference 32, 307–314 (1968).
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 27: Sorting Networks, pp.704–724.
* D.E. Knuth. "The Art of Computer Programming", Volume 3: "Sorting and Searching", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.
*.
* M. S. Paterson, "Improved sorting networks with O"(log "N") "depth", Algorithmica 5 (1990), no. 1, pp. 75–92, doi|10.1007/BF01840378.

External links

* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm Sorting Networks]
* [http://www.cs.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html Sorting Networks]
* [http://pages.ripco.net/~jgamble/nw.html List of Sorting Networks]
* [http://www.cs.brandeis.edu/~hugues/sorting_networks.html Sorting networks and the END algorithm]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… …   Wikipedia

  • Network of Workstations — A Network of Workstations (NOW) is a computer network that connects several computer workstations together with special software forming a cluster. A Cluster of Workstations (COW) is sometimes used as an alternate term.In 1996 researchers at… …   Wikipedia

  • List of network theory topics — Network theory is an area of applied mathematics. This page is a list of network theory topics. See also List of graph theory topics. Contents 1 Network theorems 2 Network properties 3 Network theory applications …   Wikipedia

  • Topological sorting — Dependency resolution redirects here. For other uses, see Dependency (disambiguation). In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes… …   Wikipedia

  • Autophagy network — consists of enzymes and substrates involved in the degradation of a cell s own components. Network membersThe Autophagy network members (gene name and aliases) as published in the last 500 newest PubMed entries (see below) are depicted… …   Wikipedia

  • Batcher odd–even mergesort — Visualization of the odd–even mergesort network with eight inputs Batcher s odd–even mergesort is a generic construction devised by Ken Batcher for sorting networks of size O(n (log n)2) and depth O((log n)2), where n is the number …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Bogosort — Class Sorting algorithm Data structure Array Worst case performance [1] Best case performance Ω …   Wikipedia

  • Odd–even sort — Example of odd even transposition sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”