Sorting network
From Wikipedia, the free encyclopedia
A sorting network is an abstract 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.
A physical sorting network can be implemented in hardware for any fixed number of elements. It operates in time proportional to the network's depth; by exploiting massive parallelism, such a device allows sorting exponentially more quickly than a sorting algorithm running on a conventional microprocessor. Examples of serial sorting algorithms that can be implemented as sorting networks are Bubble sort, Odd-even transposition sort, Odd-even merge sort, Bitonic sort, and Shellsort.
In spite of the simple statement of the problem, sorting network theory is surprisingly deep and complex. Recent attempts at using genetic algorithms to optimise sorting networks have given results which have improved on decades of work by mathematicians and engineers.
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 asymptotical 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. 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
[edit] References
- K.E. Batcher, 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. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) sorting network (Sorting in clogn parallel steps). Combinatorica 3(1), 1-19, 1983.
[edit] See also
[edit] External links
- Implementation of Sorting Networks with low branching
- Sorting Networks
- Sorting Networks
- List of Sorting Networks
- Sorting networks and the END algorithm
