chap28.htm

介绍算法的书籍

Thus, the comparator produces the values<I> f </I>(min(<I>x,y</I>)) and <I>f </I>(max(<I>x,y</I>)) when <I>f </I>(<I>x</I>) and <I>f </I>(<I>y</I>) are its inputs, which completes the proof of the claim.<P>
<img src="640_a.gif"><P>
<h4><a name="091f_1928">Figure 28.4 The operation of the comparator in the proof of Lemma 28.1. The function f is monotonically increasing.<a name="091f_1928"></sub></sup></h4><P>
We can use induction on the depth of each wire in a general comparison network to prove a stronger result than the statement of the lemma: if a wire assumes the value <I>a<SUB>i</I></SUB> when the input sequence <I>a</I> is applied to the network, then it assumes the value <I>f</I>(<I>a<SUB>i</I></SUB>) when the input sequence <I>f</I>(<I>a</I>) is applied. Because the output wires are included in this statement, proving it will prove the lemma.<P>
For the basis, consider a wire at depth 0, that is, an input wire <I>a<SUB>i</I></SUB>. The result follows trivially: when <I>f</I>(<I>a</I>) is applied to the network, the input wire carries <I>f</I>(<I>a<SUB>i</I></SUB>). For the inductive step, consider a wire at depth <I>d</I>, where <I>d </I><img src="../images/gteq.gif"> 1. The wire is the output of a comparator at depth<I> d</I>, and the input wires to this comparator are at a depth strictly less than <I>d</I>. By the inductive hypothesis, therefore, if the input wires to the comparator carry values <I>a<SUB>i</I></SUB> and <I>a<SUB>j</I></SUB> when the input sequence<I> a </I>is applied, then they carry <I>f</I>(<I>a<SUB>i</I></SUB>) and <I>f</I>(<I>a<SUB>j</I></SUB>) when the input sequence <I>f</I>(<I>a</I>) is applied. By our earlier claim, the output wires of this comparator then carry<I> f</I>(min(<I>a<SUB>i</I></SUB>, <I>a<SUB>j</I></SUB>)) and <I>f</I>(max(<I>a<SUB>i</I></SUB>, <I>a<SUB>j</I></SUB>)). Since they carry min(<I>a<SUB>i</I></SUB>, <I>a<SUB>j</I></SUB>) and max(<I>a<SUB>i</I></SUB>, <I>a<SUB>j</I></SUB>) when the input sequence is <I>a</I>, the lemma is proved.      <P>
As an example of the application of Lemma 28.1, Figure 28.5 shows the sorting network from Figure 28.2 with the monotonically increasing function<I> f</I>(<I>x</I>) = <FONT FACE="Courier New" SIZE=2><img src="../images/hfbrul14.gif"></FONT>x/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrur14.gif"></FONT> applied to the inputs. The value on every wire is <I>f</I> applied to the value on the same wire in Figure 28.2.<P>
When a comparison network is a sorting network, Lemma 28.1 allows us to prove the following remarkable result.<P>
<a name="091f_1929">Theorem 28.2<a name="091f_1929"><P>
If a comparison network with <I>n</I> inputs sorts all 2<I><SUP>n</I></SUP> possible sequences of 0's and 1<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s correctly, then it sorts all sequences of arbitrary numbers correctly.<P>
<img src="641_a.gif"><P>
<h4><a name="091f_192a">Figure 28.5 (a) The sorting network from Figure 28.2 with input sequence <img src="../images/lftwdchv.gif">9, 5, 2, 6<img src="../images/wdrtchv.gif">. (b) The same sorting network with the monotonically increasing function f(x) = f(<img src="../images/hfbrul14.gif">x/2<img src="../images/hfbrur14.gif">) applied to the inputs. Each wire in this network has the value of f applied to the value on the corresponding wire in (a).<a name="091f_192a"></sub></sup></h4><P>
<I><B>Proof     </I></B>Suppose for the purpose of contradiction that the network sorts all zero-one sequences, but there exists a sequence of arbitrary numbers that the network does not correctly sort. That is, there exists an input sequence <img src="../images/lftwdchv.gif"><I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB><img src="../images/wdrtchv.gif"> containing elements <I>a<SUB>i</I></SUB> and <I>a<SUB>j</I></SUB> such that <I>a<SUB>i</I></SUB> &lt; <I>a<SUB>j</I></SUB>, but the network places <I>a<SUB>j</SUB> </I>before <I>a<SUB>i</SUB> </I>in the output sequence. We define a monotonically increasing function<I> f</I> as<P>
<img src="641_b.gif"><P>
Since the network places <I>a<SUB>j</I></SUB> before <I>a<SUB>i</I></SUB> in the output sequence when <img src="../images/lftwdchv.gif"><I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB><img src="../images/wdrtchv.gif"> is input, it follows from Lemma 28.1 that it places <I>f</I>(<I>a<SUB>j</I></SUB>) before <I>f</I>(<I>a<SUB>i</I></SUB>) in the output sequence when <img src="../images/lftwdchv.gif"><I>f</I>(<I>a</I><SUB>1</SUB>), <I>f</I>(<I>a</I><SUB>2</SUB>), . . . , <I>f</I>(<I>a<SUB>n</I></SUB>)<img src="../images/wdrtchv.gif"> is input. But since<I> f</I>(<I>a<SUB>j</I></SUB>) = 1 and <I>f</I>(<I>a<SUB>i</I></SUB>) = 0, we obtain the contradiction that the network fails to sort the zero-one sequence <img src="../images/lftwdchv.gif"><I>f</I>(<I>a</I><SUB>1</SUB>), <I>f</I>(<I>a</I><SUB>2</SUB>), . . . , <I>f</I>(<I>a<SUB>n</I></SUB>)<img src="../images/wdrtchv.gif"> correctly.      <P>





<h2><a name="0920_1927">Exercises<a name="0920_1927"></h2><P>
<a name="0920_1928">28.2-1<a name="0920_1928"><P>
Prove that applying a monotonically increasing function to a sorted sequence produces a sorted sequence.<P>
<a name="0920_1929">28.2-2<a name="0920_1929"><P>
Prove that a comparison network with <I>n</I> inputs correctly sorts the input sequence <img src="../images/lftwdchv.gif"><I>n, n</I> - 1, . . . , 1<img src="../images/wdrtchv.gif"> if and only if it correctly sorts the <I>n</I> - 1 zero-one sequences <img src="../images/lftwdchv.gif">1, 0, 0, . . . , 0, 0<img src="../images/wdrtchv.gif">, <img src="../images/lftwdchv.gif">1, 1, 0, . . . , 0, 0<img src="../images/wdrtchv.gif">, . . . , <img src="../images/lftwdchv.gif">1, 1, 1, . . . , 1, 0<img src="../images/wdrtchv.gif">.<P>
<a name="0920_192a">28.2-3<a name="0920_192a"><P>
Use the zero-one principle to prove that the comparison network shown in Figure 28.6 is a sorting network.<P>
<a name="0920_192b">28.2-4<a name="0920_192b"><P>
<a name="0920_1926">State and prove an analog of the zero-one principle for a decision-tree model. (<I>Hint:</I> Be sure to handle equality properly.)<P>
<img src="642_a.gif"><P>
<h4><a name="0920_192c">Figure 28.6 A sorting network for sorting 4 numbers.<a name="0920_192c"></sub></sup></h4><P>
<a name="0920_192d">28.2-5<a name="0920_192d"><P>
Prove that an <I>n</I>-input sorting network must contain at least one comparator between the <I>i</I>th and (<I>i</I> + 1 )st lines for all <I>i</I> = 1, 2, . . . , <I>n</I> - 1.<P>
<P>


<P>







<h1><a name="0921_192c">28.3 A bitonic sorting network<a name="0921_192c"></h1><P>
<a name="0921_1927"><a name="0921_1928"><a name="0921_1929"><a name="0921_192a"><a name="0921_192b">The first step in our construction of an efficient sorting network is to construct a comparison network that can sort any <I><B>bitonic sequence:</I></B> a sequence that either monotonically increases and then monotonically decreases, or else monotonically decreases and then monotonically increases. For example, the sequences <img src="../images/lftwdchv.gif">1, 4, 6, 8, 3, 2<img src="../images/wdrtchv.gif"> and <img src="../images/lftwdchv.gif">9, 8, 3, 2, 4, 6<img src="../images/wdrtchv.gif"> are both bitonic. The zero-one sequences that are bitonic have a simple structure. They have the form 0<I><SUP>i</I></SUP>1<I><SUP>j</I></SUP>0<I><SUP>k</I></SUP> or the form 1<I><SUP>i</I></SUP>0<I><SUP>j</I></SUP>1<I><SUP>k</I></SUP>, for some <I>i</I>, <I>j</I>, <I>k</I> <img src="../images/gteq.gif"> 0. Note that a sequence that is either monotonically increasing or monotonically decreasing is also bitonic.<P>
The bitonic sorter that we shall construct is a comparison network that sorts bitonic sequences of 0's and 1's. Exercise 28.3-6 asks you to show that the bitonic sorter can sort bitonic sequences of arbitrary numbers.<P>





<h2>The half-cleaner</h2><P>
<a name="0922_192c">A bitonic sorter is comprised of several stages, each of which is called a <I><B>half-cleaner</I></B>. Each half-cleaner is a comparison network of depth 1 in which input line<I> i </I>is compared with line <I>i</I> + <I>n</I>/2 for <I>i</I> = 1, 2, . . . , <I>n</I>/2. (We assume that <I>n</I> is even.) Figure 28.7 shows <FONT FACE="Courier New" SIZE=2>HALF</FONT>-<FONT FACE="Courier New" SIZE=2>CLEANER</FONT>[8], the half-cleaner with 8 inputs and 8 outputs.<P>
<a name="0922_192d">When a bitonic sequence of 0's and 1's is applied as input to a half-cleaner, the half-cleaner produces an output sequence in which smaller values are in the top half, larger values are in the bottom half, and both halves are bitonic. In fact, at least one of the halves is <I><B>clean</I></B>--consisting of either all 0's or all 1's--and it is from this property that we derive the name &quot;half-cleaner.&quot; (Note that all clean sequences are bitonic.) The next lemma proves these properties of half-cleaners.<P>
<img src="643_a.gif"><P>
<h4><a name="0922_192e">Figure 28.7 The comparison network <FONT FACE="Courier New" SIZE=2>HALF-CLEANER[8]</FONT>. Two different sample zero-one input and output values are shown. The input is assumed to be bitonic. A half-cleaner ensures that every output element of the top half is at least as small as every output element of the bottom half. Moreover, both halves are bitonic, and at least one half is clean.<a name="0922_192e"></sub></sup></h4><P>
<a name="0922_192f">Lemma 28.3<a name="0922_192f"><P>
If the input to a half-cleaner is a bitonic sequence of 0's and 1's, then the output satisfies the following properties: both the top half and the bottom half are bitonic, every element in the top half is at least as small as every element of the bottom half, and at least one half is clean.<P>
<I><B>Proof     </I></B>The comparison network <FONT FACE="Courier New" SIZE=2>HALF</FONT>-<FONT FACE="Courier New" SIZE=2>CLEANER</FONT>[<I>n</I>] compares inputs<I> i</I> and <I>i</I> + <I>n</I>/2 for <I>i</I> = 1, 2, . . . , <I>n</I>/2. Without loss of generality, suppose that the input is of the form 00 . . . 011 . . . 100 . . . 0. (The situation in which the input is of the form 11 . . . 100 . . . 011 . . . 1 is symmetric.) There are three possible cases depending upon the block of consecutive 0's or 1s in which the midpoint<I> n</I>/2 falls, and one of these cases (the one in which the midpoint occurs in the block of 1<FONT FACE="CG Times (W1)" SIZE=2>'</FONT>s) is further split into two cases. The four cases are shown in Figure 28.8. In each case shown, the lemma holds.      <P>
<P>







<h2>The bitonic sorter</h2><P>
<a name="0923_192e">By recursively combining half-cleaners, as shown in Figure 28.9, we can build a <I><B>bitonic sorter</I></B>, which is a network that sorts bitonic sequences. The first stage of <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>] consists of <FONT FACE="Courier New" SIZE=2>HALF</FONT>-<FONT FACE="Courier New" SIZE=2>CLEANER</FONT>[<I>n</I>], which, by Lemma 28.3, produces two bitonic sequences of half the size such that every element in the top half is at least as small as every element in the bottom half. Thus, we can complete the sort by using two copies of <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>/2] to sort the two halves recursively. In Figure 28.9(a), the recursion has been shown explicitly, and in Figure 28.9(b), the recursion has been unrolled to show the progressively smaller half-cleaners that make up the remainder of the bitonic sorter. The depth <I>D</I>(<I>n</I>) of <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>] is given by the recurrence whose solution is <I>D</I>(<I>n</I>) = lg <I>n</I>.<P>
<img src="644_a.gif"><P>
<h4><a name="0923_192f">Figure 28.8 The possible comparisons in <FONT FACE="Courier New" SIZE=2>HALF<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>CLEANER<FONT FACE="Times New Roman" SIZE=2>[n]. </FONT></FONT></FONT></FONT>The input sequence is assumed to be a bitonic sequence of 0's and 1<FONT FACE="CG Times (W1)" SIZE=2>'<FONT FACE="Times New Roman" SIZE=2></FONT></FONT>s, and without loss of generality, we assume that it is of the form 00 . . . 011 . . . 100 . . . 0. Subsequences of 0<FONT FACE="CG Times (W1)" SIZE=2>'<FONT FACE="Times New Roman" SIZE=2></FONT></FONT>s are white, and subsequences of 1's are gray. We can think of the n inputs as being divided into two halves such that for i = 1, 2, . . . , n/2, inputs i and i + n/2 are compared. (a)-(b) Cases in which the division occurs in the middle subsequence of 1<FONT FACE="CG Times (W1)" SIZE=2>'</FONT><FONT FACE="Times New Roman" SIZE=2>s. (c)-(d) </FONT>Cases in which the division occurs in a subsequence of 0<FONT FACE="CG Times (W1)" SIZE=2>'<FONT FACE="Times New Roman" SIZE=2></FONT></FONT>s. For all cases, every element in the top half is at least as small as every element in the bottom half, both halves are bitonic, and at least one half is clean.<a name="0923_192f"></sub></sup></h4><P>
<img src="645_a.gif"><P>
<h4><a name="0923_1930">Figure 28.9 The comparison network <FONT FACE="Courier New" SIZE=2>BITONIC-SORTER</FONT>[n], shown here for n = 8. (a) The recursive construction: <FONT FACE="Courier New" SIZE=2>HALF-CLEANER</FONT>[n] followed by two copies of <FONT FACE="Courier New" SIZE=2>BITONIC-SORTER</FONT>[n/2] that operate in parallel. (b) The network after unrolling the recursion. Each half-cleaner is shaded. Sample zero-one values are shown on the wires.<a name="0923_1930"></sub></sup></h4><P>
<img src="645_b.gif"><P>
Thus, a zero-one bitonic sequence can be sorted by <FONT FACE="Courier New" SIZE=2>BITONIC</FONT>-<FONT FACE="Courier New" SIZE=2>SORTER</FONT>, which has a depth of lg <I>n</I>. It follows by the analog of the zero-one principle given as Exercise 28.3-6 that any bitonic sequence of arbitrary numbers can be sorted by this network.<P>
<P>