chap28.htm

介绍算法的书籍

<h2><a name="0924_1930">Exercises<a name="0924_1930"></h2><P>
<a name="0924_1931">28.3-1<a name="0924_1931"><P>
How many bitonic sequences of 0's and 1's are there?<P>
<a name="0924_1932">28.3-2<a name="0924_1932"><P>
Show that <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>], where <I>n</I> is an exact power of 2, contains <img src="../images/bound.gif">(<I>n </I>lg <I>n</I>) comparators.<P>
<a name="0924_1933">28.3-3<a name="0924_1933"><P>
Describe how an <I>O</I>(lg <I>n</I>)-depth bitonic sorter can be constructed when the number <I>n</I> of inputs is not an exact power of 2.<P>
<a name="0924_1934">28.3-4<a name="0924_1934"><P>
If the input to a half-cleaner is a bitonic sequence of arbitrary numbers, prove that the output satisfies the following properties: both the top half and the bottom half are bitonic, and every element in the top half is at least as small as every element in the bottom half.<P>
<a name="0924_1935">28.3-5<a name="0924_1935"><P>
Consider two sequences of 0's and 1's. Prove that if every element in one sequence is at least as small as every element in the other sequence, then one of the two sequences is clean.<P>
<a name="0924_1936">28.3-6<a name="0924_1936"><P>
<a name="0924_192f">Prove the following analog of the zero-one principle for bitonic sorting networks: a comparison network that can sort any bitonic sequence of 0<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s and 1<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s can sort any bitonic sequence of arbitrary numbers.<P>
<P>


<P>







<h1><a name="0925_1934">28.4 A merging network<a name="0925_1934"></h1><P>
<a name="0925_1930"><a name="0925_1931"><a name="0925_1932"><a name="0925_1933">Our sorting network will be constructed from <I><B>merging networks</I></B>, which are networks that can merge two sorted input sequences into one sorted output sequence. We modify <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>] to create the merging network <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[<I>n</I>]. As with the bitonic sorter, we shall prove the correctness of the merging network only for inputs that are zero-one sequences. Exercise 28.4-1 asks you to show how the proof can be extended to arbitrary input values.<P>
The merging network is based on the following intuition. Given two sorted sequences, if we reverse the order of the second sequence and then concatenate the two sequences, the resulting sequence is bitonic. For example, given the sorted zero-one sequences <I>X</I> = 00000111 and <I>Y</I> = 00001111, we reverse <I>Y</I> to get <I>Y</I><SUP>R</SUP> = 11110000. Concatenating <I>X </I>and <I>Y</I><SUP>R</SUP> yields 0000011111110000, which is bitonic. Thus, to merge the two input sequences <I>X</I> and <I>Y</I>, it suffices to perform a bitonic sort on <I>X </I>concatenated with <I>Y</I><SUP>R</sup>.<P>
We can construct <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[<I>n</I>] by modifying the first half-cleaner of <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>]. The key is to perform the reversal of the the second half of the inputs implicitly. Given two sorted sequences <img src="../images/lftwdchv.gif"><I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I>/2</SUB><img src="../images/wdrtchv.gif"> and <img src="../images/lftwdchv.gif"><I>a<SUB>n</I>/2+1</SUB>, <I>a<SUB>n</I>/2+2</SUB>, . . . , <I>a<SUB>n</I></SUB><img src="../images/wdrtchv.gif"> to be merged, we want the effect of bitonically sorting the sequence <img src="../images/lftwdchv.gif"><I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I>/2</SUB>, <I>a</I><SUB>n</SUB>, <I>a<SUB>n-</I>1</SUB>,<SUB> . . . </SUB>,<SUB> </SUB><I>a<SUB>n</I>/2+1</SUB><img src="../images/wdrtchv.gif">. Since the half-cleaner of <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>] compares inputs <I>i</I> and <I>n</I>/2 + <I>i</I>, for <I>i</I> = 1, 2, . . . , <I>n</I>/2, we make the first stage of the merging network compare inputs <I>i</I> and <I>n</I> - <I>i</I> + 1. Figure 28.10 shows the correspondence. The only subtlety is that the order of the outputs from the bottom of the first stage of <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[<I>n</I>] are reversed compared with the order of outputs from an ordinary half-cleaner. Since the reversal of a bitonic sequence is bitonic, however, the top and bottom outputs of the first stage of the merging network satisfy the properties in Lemma 28.3, and thus the top and bottom can be bitonically sorted in parallel to produce the sorted output of the merging network.<P>
<img src="647_a.gif"><P>
<h4><a name="0925_1935">Figure 28.10 Comparing the first stage of <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[n] with <FONT FACE="Courier New" SIZE=2>HALF-CLEANER</FONT>[n], for n = 8. (a) The first stage of <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[n] transforms the two monotonic input sequences <img src="../images/lftwdchv.gif">a<SUB>1</SUB>, a<SUB>2</SUB>, . . . , a<SUB>n/2</SUB><img src="../images/wdrtchv.gif"> and <img src="../images/lftwdchv.gif">a<SUB>n/2+1</SUB>, a<SUB>n/2+2</SUB>, . . . , a<SUB>n</SUB><img src="../images/wdrtchv.gif"> into two bitonic sequences <img src="../images/lftwdchv.gif">b<SUB>1</SUB>, b<SUB>2</SUB>, . . . , b<SUB>n/2</SUB><img src="../images/wdrtchv.gif"> and <img src="../images/lftwdchv.gif">b<SUB>n/2+1</SUB>, b<SUB>n/2+2</SUB>, . . . , b<SUB>n</SUB><img src="../images/wdrtchv.gif">. (b) The equivalent operation for <FONT FACE="Courier New" SIZE=2>HALF-CLEANER</FONT>[n]. The bitonic input sequence <img src="../images/lftwdchv.gif">a<SUB>1</SUB>, a<SUB>2</SUB>, . . . , a<SUB>n/2-1</SUB>, a<SUB>n/2</SUB>, a<SUB>n</SUB>, a<SUB>n-1</SUB>, . . . , a<SUB>n/2+2</SUB>, a<SUB>n/2+1</SUB><img src="../images/wdrtchv.gif"> is transformed into the two bitonic sequences <img src="../images/lftwdchv.gif">b<SUB>1</SUB>, b<SUB>2</SUB>, . . . , b<SUB>n/2</SUB><img src="../images/wdrtchv.gif"> and <img src="../images/lftwdchv.gif">b<SUB>n</SUB>, b<SUB>n-1</SUB>, . . . , b<SUB>n/2+1</SUB><img src="../images/wdrtchv.gif">.<a name="0925_1935"></sub></sup></h4><P>
<img src="647_b.gif"><P>
<h4><a name="0925_1936">Figure 28.11 A network that merges two sorted input sequences into one sorted output sequence. The network <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[n] can be viewed as <FONT FACE="Courier New" SIZE=2>BITONIC-SORTER</FONT>[n] with the first half-cleaner altered to compare inputs i and n - i + 1 for i = 1, 2, . . . , n/2. Here, n = 8. (a) The network decomposed into the first stage followed by two parallel copies of <FONT FACE="Courier New" SIZE=2>BITONIC-SORTER</FONT>[n/2]. (b) The same network with the recursion unrolled. Sample zero-one values are shown on the wires, and the stages are shaded.<a name="0925_1936"></sub></sup></h4><P>
The resulting merging network is shown in Figure 28.11. Only the first stage of <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[<I>n</I>] is different from <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>]. Consequently, the depth of <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[<I>n</I>] is lg <I>n</I>, the same as that of <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>].<P>





<h2><a name="0926_1936">Exercises<a name="0926_1936"></h2><P>
<a name="0926_1937">28.4-1<a name="0926_1937"><P>
<a name="0926_1934">Prove an analog of the zero-one principle for merging networks. Specifically, show that a comparison network that can merge any two monotonically increasing sequences of 0's and 1's can merge any two monotonically increasing sequences of arbitrary numbers.<P>
<a name="0926_1938">28.4-2<a name="0926_1938"><P>
How many different zero-one input sequences must be applied to the input of a comparison network to verify that it is a merging network?<P>
<a name="0926_1939">28.4-3<a name="0926_1939"><P>
Show that any network that can merge 1 item with <I>n</I> - 1 items to produce a sorted sequence of length <I>n</I> must have depth at least lg <I>n</I>.<P>
<a name="0926_193a">28.4-4<a name="0926_193a"><P>
<a name="0926_1935">Consider a merging network with inputs <I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB>, for <I>n</I> an exact power of 2, in which the two monotonic sequences to be merged are <img src="../images/lftwdchv.gif"><I>a</I><SUB>1</SUB>, <I>a</I><SUB>3</SUB>, . . . , <I>a<SUB>n-</I>1</SUB><img src="../images/wdrtchv.gif"> and <img src="../images/lftwdchv.gif"><I>a</I><SUB>2</SUB>, <I>a</I><SUB>4</SUB>, . . . , <I>a<SUB>n</I></SUB><img src="../images/wdrtchv.gif">. Prove that the number of comparators in this kind of merging network is <img src="../images/omega12.gif">(<I>n</I> lg <I>n</I>). Why is this an interesting lower bound? (<I>Hint:</I> Partition the comparators into three sets.)<P>
<a name="0926_193b">28.4-5<a name="0926_193b"><P>
Prove that any merging network, regardless of the order of inputs, requires <img src="../images/omega12.gif">(<I>n</I> lg <I>n</I>) comparators.<P>
<P>


<P>







<h1><a name="0927_1939">28.5 A sorting network<a name="0927_1939"></h1><P>
<a name="0927_1936"><a name="0927_1937"><a name="0927_1938">We now have all the necessary tools to construct a network that can sort any input sequence. The sorting network <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>] uses the merging network to implement a parallel version of merge sort from Section 1.3.1. The construction and operation of the sorting network are illustrated in Figure 28.12.<P>
Figure 28.12(a) shows the recursive construction of <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>]. The <I>n </I>input elements are sorted by using two copies of <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>/2] recursively to sort (in parallel) two subsequences of length <I>n</I>/2 each. The two resulting sequences are then merged by <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[<I>n</I>]. The boundary case for the recursion is when <I>n</I> = 1, in which case we can use a wire to sort the 1-element sequence, since a 1-element sequence is already sorted. Figure 28.12(b) shows the result of unrolling the recursion, and Figure 28.12(c) shows the actual network obtained by replacing the <FONT FACE="Courier New" SIZE=2>MERGER</FONT> boxes in Figure 28.12(b) with the actual merging networks.<P>
<img src="649_a.gif"><P>
<h4><a name="0927_193a">Figure 28.12 The sorting network <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[n] constructed by recursively combining merging networks. (a) The recursive construction. (b) Unrolling the recursion. (c) Replacing the <FONT FACE="Courier New" SIZE=2>MERGER</FONT> boxes with the actual merging networks. The depth of each comparator is indicated, and sample zero-one values are shown on the wires.<a name="0927_193a"></sub></sup></h4><P>
Data pass through lg <I>n</I> stages in the network <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>]. Each of the individual inputs to the network is already a sorted 1-element sequence. The first stage of <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>] consists of <I>n</I>/2 copies of <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[2] that work in parallel to merge pairs of 1-element sequences to produce sorted sequences of length 2. The second stage consists of <I>n</I>/4 copies of <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[4] that merge pairs of these 2-element sorted sequences to produce sorted sequences of length 4. In general, for <I>k</I> = 1, 2, . . . , lg <I>n</I>, stage <I>k</I> consists of <I>n</I>/2<I><SUP>k</I></SUP> copies of <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[2<I><SUP>k</I></SUP>] that merge pairs of the 2<I><SUP>k</I>-1</SUP>-element sorted sequences to produce sorted sequences of length 2<I><SUP>k</I></SUP>. At the final stage, one sorted sequence consisting of all the input values is produced. This sorting network can be shown by induction to sort zero-one sequences, and consequently, by the zero-one principle (Theorem 28.2), it can sort arbitrary values.<P>
We can analyze the depth of the sorting network recursively. The depth <I>D</I>(<I>n</I>) of <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>] is the depth <I>D</I>(<I>n</I>/2) of <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>/2] (there are two copies of <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>/2], but they operate in parallel) plus the depth lg <I>n</I> of <FONT FACE="Courier New" SIZE=2>MERGER</FONT>[<I>n</I>]. Consequently, the depth of <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>] is given by the recurrence<P>
<img src="650_a.gif"><P>
whose solution is <I>D(n)</I> = <img src="../images/bound.gif">(lg<SUP>2</SUP> <I>n</I>). Thus, we can sort <I>n</I> numbers in parallel in <I>O</I>(lg<SUP>2</SUP> <I>n</I>) time.<P>