HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform
sorting Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. # ordering: arranging items in a sequence ordered by some criterion; # categorizing: grouping items with similar pro ...
on fixed numbers of values, in which case they are called sorting networks. Sorting networks differ from general
comparison sort A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should o ...
s in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. In order to sort larger amounts of inputs, new sorting networks must be constructed. This independence of comparison sequences is useful for parallel execution and for implementation in hardware. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor, who subsequently patented the idea. Sorting networks can be implemented either in hardware or in
software Software is a set of computer programs and associated documentation and data. This is in contrast to hardware, from which the system is built and which actually performs the work. At the lowest programming level, executable code consist ...
.
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
describes how the comparators for binary integers can be implemented as simple, three-state electronic devices. Batcher, in 1968, suggested using them to construct switching networks for computer hardware, replacing both
buses A bus (contracted from omnibus, with variants multibus, motorbus, autobus, etc.) is a road vehicle that carries significantly more passengers than an average car or van. It is most commonly used in public transport, but is also in use for cha ...
and the faster, but more expensive,
crossbar switch In electronics and telecommunications, a crossbar switch (cross-point switch, matrix switch) is a collection of switches arranged in a matrix configuration. A crossbar switch has multiple input and output lines that form a crossed pattern of int ...
es. Since the 2000s, sorting nets (especially bitonic mergesort) are used by the
GPGPU General-purpose computing on graphics processing units (GPGPU, or less often GPGP) is the use of a graphics processing unit (GPU), which typically handles computation only for computer graphics, to perform computation in applications traditiona ...
community for constructing sorting algorithms to run on
graphics processing unit A graphics processing unit (GPU) is a specialized electronic circuit designed to manipulate and alter memory to accelerate the creation of images in a frame buffer intended for output to a display device. GPUs are used in embedded systems, m ...
s.


Introduction

A sorting network consists of two types of items: comparators and wires. The wires are thought of as running from left to right, carrying values (one per wire) that traverse the network all at the same time. Each comparator connects two wires. When a pair of values, traveling through a pair of wires, encounter a comparator, the comparator swaps the values
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
the top wire's value is greater or equal to the bottom wire's value. In a formula, if the top wire carries and the bottom wire carries , then after hitting a comparator the wires carry x' = \min(x, y) and y' = \max(x, y), respectively, so the pair of values is sorted. A network of wires and comparators that will correctly sort all possible inputs into ascending order is called a sorting network or Kruskal hub. By reflecting the network, it is also possible to sort all inputs into descending order. The full operation of a simple sorting network is shown below. It is evident 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 sorts out the middle two wires.


Depth and efficiency

The efficiency of a sorting network can be measured by its total size, meaning the number of comparators in the network, or by its ''depth'', defined (informally) as the largest number of comparators that any input value can encounter on its way through the network. Noting that sorting networks can perform certain comparisons
in parallel Two-terminal components and electrical networks can be connected in series or parallel. The resulting electrical network will have two terminals, and itself can participate in a series or parallel topology. Whether a two-terminal "object" is a ...
(represented in the graphical notation by comparators that lie on the same vertical line), and assuming all comparisons to take unit time, it can be seen that the depth of the network is equal to the number of time steps required to execute it.


Insertion and Bubble 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 sort Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Ho ...
). 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, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passe ...
). 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. The insertion network (or equivalently, bubble network) has a depth of , where is the number of values. This is better than the time needed by
random-access machine In computer science, random-access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers. Like the c ...
s, but it turns out that there are much more efficient sorting networks with a depth of just , as described
below Below may refer to: *Earth *Ground (disambiguation) *Soil *Floor *Bottom (disambiguation) *Less than *Temperatures below freezing *Hell or underworld People with the surname *Ernst von Below (1863–1955), German World War I general *Fred Below ( ...
.


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 permutations of numbers in an -wire network, and to test all of them would take a significant amount of time, especially when is large. The number of test cases can be reduced significantly, to , using the so-called zero-one principle. While still exponential, this is smaller than for all , and the difference grows quite quickly with increasing . The zero-one principle states that, if a sorting network can correctly sort all sequences of zeros and ones, then it is also valid for arbitrary ordered inputs. 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 can be proven by first observing the following fact about comparators: when a
monotonically increasing In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of orde ...
function is applied to the inputs, i.e., and are replaced by and , then the comparator produces and . By induction on the depth of the network, this result can be extended to a
lemma Lemma may refer to: Language and linguistics * Lemma (morphology), the canonical, dictionary or citation form of a word * Lemma (psycholinguistics), a mental abstraction of a word about to be uttered Science and mathematics * Lemma (botany), ...
stating that if the network transforms the sequence into , it will transform into . Suppose that some input contains two items , and the network incorrectly swaps these in the output. Then it will also incorrectly sort for the function : f(x) = \begin 1\ &\mbox x > a_i \\ 0\ &\mbox \end This function is monotonic, so we have the zero-one principle as the
contrapositive In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a stat ...
.


Constructing sorting networks

Various algorithms exist to construct sorting networks of depth (hence size ) such as Batcher odd–even mergesort,
bitonic sort Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O(n\log^2(n)) comparators and have ...
, Shell sort, and the Pairwise sorting network. These networks are often used in practice. It is also possible to construct networks of depth (hence size ) using a construction called the ''AKS network'', after its discoverers Ajtai, Komlós, and Szemerédi. While an important theoretical discovery, the AKS network has very limited practical application because of the large linear constant hidden by the
Big-O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
. These are partly due to a construction of an
expander graph In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applica ...
. A simplified version of the AKS network was described by Paterson in 1990, who noted that "the constants obtained for the depth bound still prevent the construction being of practical value". A more recent construction called the ''zig-zag sorting network'' of size was discovered by Goodrich in 2014. While its size is much smaller than that of AKS networks, its depth makes it unsuitable for a parallel implementation.


Optimal sorting networks

For small, fixed numbers of inputs , ''optimal'' sorting networks can be constructed, with either minimal depth (for maximally parallel execution) or minimal size (number of comparators). These networks can be used to increase the performance of larger sorting networks resulting from the
recursive Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
constructions of, e.g., Batcher, by halting the recursion early and inserting optimal nets as base cases. The following table summarizes the optimality results for small networks for which the optimal depth is known: For larger networks neither the optimal depth nor the optimal size are currently known. The bounds known so far are provided in the table below: The first sixteen depth-optimal networks are listed in Knuth's ''
Art of Computer Programming ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of com ...
'', Section 5.3.4: Networks for Sorting. and have been since the 1973 edition; however, while the optimality of the first eight was established by Floyd and Knuth in the 1960s, this property wasn't proven for the final six until 2014 (the cases nine and ten having been decided in 1991). For one to eleven inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes can be derived inductively using a lemma due to Van Voorhis (p. 240): . The first ten optimal networks have been known since 1969, with the first eight again being known as optimal since the work of Floyd and Knuth, but optimality of the cases and took until 2014 to be resolved. An optimal network for size 11 was found in December 2019 by Jannis Harder, which also made the lower bound for 12 match its upper bound. Some work in designing optimal sorting network has been done using
genetic algorithm In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to ge ...
s: D. Knuth mentions that the ''smallest'' known sorting network for was found by Hugues Juillé in 1995 "by simulating an evolutionary process of genetic breeding" (p. 226), and that the ''minimum depth'' sorting networks for and were found by Loren Schwiebert in 2001 "using genetic methods" (p. 229).


Complexity of testing sorting networks

Unless
P=NP The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used above ...
, the problem of testing whether a candidate network is a sorting network is likely to remain difficult for networks of large sizes, due to the problem being
co-NP In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely ...
-complete.


References

*


External links


List of smallest sorting networks for given number of inputsTool for generating and graphing sorting networks
*
Sorting Networks validity
{{sorting Computer engineering Sorting algorithms