Sorting network
Encyclopedia
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 sorts the values by outputting the smaller value to one wire, and the larger 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. This independence of comparison sequences is useful for parallel execution of the algorithms. Despite the simplicity of the model, sorting network theory is surprisingly deep and complex.
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.
). 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, which collapses together comparators that can be performed simultaneously shows that, in fact, they are identical.
, bitonic sort, Shell sort
, and the Pairwise sorting network
. These networks are often used in practice.
The zero-one principle states that a sorting network is valid if it can sort all 2n sequences of 0s and 1s. This not only drastically cuts down on the number of tests needed to ascertain the validity of a network, it is of great use in creating many constructions of sorting networks as well. The principle has been proven by a special case of the Bouricius's Theorem in 1954 by W. G. Bouricius.
or retrograde software analysis
(Alex Peter, 2010). Through retrograde software analysis, we analyze a network reversed in time starting from the sorted output, then going backward. If we combine the zero-one principle and retrograde analysis, we need only n test cases, in which case we have to follow gradually from 1 to 2n testing paths. If we use topology of a sorting network, we need to check at first about n2 test cases; basically we try to connect each input with each upper output using the network wiring without ever going back or down, and then we check that paths combined are independent regarding used comparators.
, Komlós
, and Szemerédi
, achieves depth O(log n) and size 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 for small c remains a fundamental open problem.
Some important progress in designing optimal sorting network is done using genetic algorithm
technique as well. (M. Mitchell, 1998)
For 1 to 8 inputs optimal sorting networks are known. They have respectively 0, 1, 3, 5, 9, 12, 16 and 19 comparators (Knuth, 1997).
The optimal depths for up to 10 inputs are known and they are respectively 0, 1, 3, 3, 5, 5, 6, 6, 7, 7.
Introduction
A sorting network consists of two items: 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 by "inserting" an additional number into the already sorted subnet (using the principle behind insertion sortInsertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge 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
Bubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
).
The structure of these two sorting networks are very similar. A construction of the two different variants, which 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 such as Batcher odd-even mergesortBatcher odd-even mergesort
Batcher's odd–even mergesort is a generic construction devised by Ken Batcher for sorting networks of size O and depth O, where n is the number of items to be sorted...
, bitonic sort, Shell sort
Shell sort
Shellsort, also known as Shell sort or Shell's method is an in-place comparison sort. It generalizes an exchanging sort, such as insertion or bubble sort, by allowing the comparison and exchange of elements that lie far apart. Its first version was published by Donald Shell in 1959. The running...
, and the Pairwise sorting network
Pairwise sorting network
The Pairwise sorting network is a sorting network discovered and published by Ian Parberry in 1992. The pairwise sorting network has the same cost and delay as the odd-even mergesort network. It requires n/4 + n - 1 comparators and has depth /2.- External links :* – Web page by the author....
. 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 when they are larger. 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 2n sequences of 0s and 1s. This not only drastically cuts down on the number of tests needed to ascertain the validity of a network, it is of great use in creating many constructions of sorting networks as well. The principle has been proven by a special case of the Bouricius's Theorem in 1954 by W. G. Bouricius.
Topology and retrograde view
In order to reduce the number of test cases needed to assert the validity of an n-input sorting network, we can use topology of the networkNetwork topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
or retrograde software analysis
Retrograde software analysis
Retrograde software analysis is a set of software techniques related to software design, development, software testing, debugging and code analysis....
(Alex Peter, 2010). Through retrograde software analysis, we analyze a network reversed in time starting from the sorted output, then going backward. If we combine the zero-one principle and retrograde analysis, we need only n test cases, in which case we have to follow gradually from 1 to 2n testing paths. If we use topology of a sorting network, we need to check at first about n2 test cases; basically we try to connect each input with each upper output using the network wiring without ever going back or down, and then we check that paths combined are independent regarding used comparators.
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 known sorting network, called AKS network after its discoverers AjtaiMiklós Ajtai
Miklós Ajtai is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden...
, Komlós
János Komlós (mathematician)
János Komlós is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He is a professor of mathematics at Rutgers University since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy...
, and Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
, achieves depth O(log n) and size for n inputs, which is asymptotically optimal
Asymptotically optimal
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor worse than the best possible algorithm...
. 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
Expander graph
In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...
. Finding sorting networks with size for small c remains a fundamental open problem.
Some important progress in designing optimal sorting network is done using genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
technique as well. (M. Mitchell, 1998)
For 1 to 8 inputs optimal sorting networks are known. They have respectively 0, 1, 3, 5, 9, 12, 16 and 19 comparators (Knuth, 1997).
The optimal depths for up to 10 inputs are known and they are respectively 0, 1, 3, 3, 5, 5, 6, 6, 7, 7.