 |  Introduction to Algorithms, 2/e Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
Sorting Networks
Glossary
| comparator | a device with two inputs, x and y, and two outputs, x' and y', that performs the following function: x' = min(x, y), y' = max(x, y).
(See page 705)
| | | | | wire | transmits a value from place to place. Wires can connect the output of one comparator to the input of another, but otherwise they are either network input wires or network output wires.
(See page 705)
| | | | | input wires | a1, a2, . . . , an, through which the values to be sorted enter the network.
(See page 705)
| | | | | output wires | b1, b2, . . . , bn, which produce the results computed by the network.
(See page 705)
| | | | | input sequence | ⟨a1, a2, . . . , an⟩ referring to the values on the input wires.
(See page 705)
| | | | | output sequence | ⟨b1, b2, . . . , bn⟩ referring to the values on the output wires.
(See page 705)
| | | | | comparison network | a set of comparators interconnected by wires.
(See page 705)
| | | | | lines | We draw a comparison network on n inputs as a collection of n horizontal lines with comparators stretched vertically. Note that a line does not represent a single wire, but rather a sequence of distinct wires connecting various comparators.
(See page 705)
| | | | | depth | of a wire is defined as follows: An input wire of a comparison network has depth 0. Now, if a comparator has two input wires with depths dx and dy, then its output wires have depth max(dx, dy) + 1. Because there are no cycles of comparators in a comparison network, the depth of a wire is well defined, and we define the depth of a comparator to be the depth of its output wires. The depth of a comparison network is the maximum depth of an output wire or, equivalently, the maximum depth of a comparator. If each comparator takes one time unit to produce its ouput value, and if network inputs appear at time 0, a comparator at depth d produces its outputs at time d; the depth of the network therefore equals the time for the network to produce values at all of its output wires.
(See page 707)
| | | | | sorting network | a comparison network for which the output sequence is monotonically increasing (that is, b1 ≤ b2 ≤ · · · ≤ bn) for every input sequence. Not every comparison network is a sorting network.
(See page 707)
| | | | | size | the number of comparators a comparison network contains. Depends on the number of inputs and outputs.
(See page 707)
| | | | | zero-one principle | if a sorting network works correctly when each input is drawn from the set {0, 1}, then it works correctly on arbitrary input numbers. (The numbers can be integers, reals, or, in general, any set of values from any linearly ordered set.)
(See page 709)
| | | | | bitonic sequence | a sequence that monotonically increases and then monotonically decreases, or can be circularly shifted to become monotonically increasing and then monotonically decreasing.
(See page 712)
| | | | | half-cleaner | a comparison network of depth 1 in which input line i is compared with line i + n/2 for i = 1, 2, . . . , n/2. (We assume that n is even.)
(See page 712)
| | | | | clean | consisting of either all 0's or all 1's.
(See page 713)
| | | | | bitonic sorter | a network that sorts bitonic sequences.
(See page 715)
| | | | | merging networks | networks that can merge two sorted input sequences into one sorted output sequence.
(See page 716)
| | | | | transposition network | A comparison network is a transposition network if each comparator connects adjacent lines.
(See page 721)
| | | | | odd-even sorting network | An odd-even sorting network on n inputs ⟨a1, a2, . . . , an⟩ is a transposition sorting network with n levels of comparators connected in the "brick-like" pattern.
(See page 721)
| | | | | odd-even merging network | If n is an exact power of 2, we wish to merge the sorted sequence of elements on lines ⟨a1, a2, . . . , an⟩ with those lines
⟨an+1, an+2, . . . , a2n⟩.
(See page 721)
| | | | | permutation network | A permutation network on n inputs and n outputs has switches that allow it to connect its inputs to its outputs according to any of the n! possible permutations.
(See page 722)
|
|
2002 McGraw-Hill Higher Education