chap28.htm

介绍算法的书籍

<h2><a name="0928_193c">Exercises<a name="0928_193c"></h2><P>
<a name="0928_193d">28.5-1<a name="0928_193d"><P>
<a name="0928_1939"><a name="0928_193a">How many comparators are there in <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>]?<P>
<a name="0928_193e">28.5-2<a name="0928_193e"><P>
<a name="0928_193b">Show that the depth of <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>] is exactly (lg <I>n</I>)(lg<I>n</I> + 1)/2.<P>
<a name="0928_193f">28.5-3<a name="0928_193f"><P>
Suppose we modify a comparator to take two sorted lists of length <I>k</I> as inputs, merge them, and output the largest <I>k</I> to its &quot;max&quot; output and the smallest <I>k</I> to its &quot;min&quot; output. Show that any sorting network on <I>n</I> inputs with comparators modified in this fashion can sort <I>nk</I> numbers, assuming that each input to the network is a sorted list of length <I>k</I>.<P>
<a name="0928_1940">28.5-4<a name="0928_1940"><P>
Suppose that we have 2<I>n</I> elements <img src="../images/lftwdchv.gif"><I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a</I><SUB>2<I>n</I></SUB><img src="../images/wdrtchv.gif"> and wish to partition them into the <I>n</I> smallest and the <I>n</I> largest. Prove that we can do this in constant additional depth after separately sorting <img src="../images/lftwdchv.gif"><I>a</I><SUB>1</SUB>,<I>a</I><SUB>2</SUB>, . . . , <I>a</I><SUB>n</SUB><img src="../images/wdrtchv.gif"> and <img src="../images/lftwdchv.gif"><I>a<SUB>n</I>+1</SUB>, <I>a<SUB>n</I>+2</SUB>, . . . , <I>a</I><SUB>2<I>n</I></SUB><img src="../images/wdrtchv.gif">.<P>
<a name="0928_1941">28.5-5<a name="0928_1941"><P>
Let <I>S</I>(<I>k</I>) be the depth of a sorting network with <I>k</I> inputs, and let <I>M</I>(<I>k</I>) be the depth of a merging network with 2<I>k</I> inputs. Suppose that we have a sequence of <I>n</I> numbers to be sorted and know that every number is within <I>k</I> positions of its correct position in the sorted order. Show that we can sort the <I>n</I> numbers in depth <I>S</I>(<I>k</I>) + 2<I>M</I>(<I>k</I>).<P>
<a name="0928_1942">28.5-6<a name="0928_1942"><P>
We can sort the elements of an <I>m</I> X <I>m</I> matrix by repeating the following procedure <I>k</I> times:<P>
1.     Sort each odd-numbered row into monotonically increasing order.<P>
2.     Sort each even-numbered row into monotonically decreasing order.<P>
3.     Sort each column into monotonically increasing order.<P>
How many iterations <I>k</I> are required for this procedure to sort, and what is the pattern of the sorted output?<P>
<P>


<P>







<h1><a name="0929_1947">Problems<a name="0929_1947"></h1><P>
<a name="0929_1948">28-1 Transposition sorting networks<a name="0929_1948"><P>
<a name="0929_193c"><a name="0929_193d">A comparison network is a <I><B>transposition network</I></B> if each comparator connects adjacent lines, as in the network in Figure 28.3.<P>
<I><B>a.</I></B>     Show that any transposition network with <I>n</I> inputs that sorts has <img src="../images/omega12.gif">(<I>n</I><SUP>2</SUP>) comparators.<P>
<I><B>b.</I></B>     Prove that a transposition network with <I>n</I> inputs is a sorting network if and only if it sorts the sequence <img src="../images/lftwdchv.gif"><I>n</I>, <I>n</I>- 1, . . . , 1<img src="../images/wdrtchv.gif">. (<I>Hint</I>: Use an induction argument analogous to the one in the proof of Lemma 28.1.)<P>
<a name="0929_193e"><a name="0929_193f"><a name="0929_1940">An <I><B>odd-even sorting network</I></B> on <I>n</I> inputs <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"> has <I>n</I> levels of comparators. Figure 28.13 shows an odd-even transposition network on 8 inputs. As can be seen in the figure, for <I>i</I> = 2, 3, . . . , <I>n</I> - 1 and <I>d</I> = 1, 2, . . . , <I>n</I>, line <I>i</I> is connected by a depth-<I>d</I> comparator to line <I>j</I> = <I>i</I> + (-1)<I><SUP>i</I>+<I>d</I></SUP> if 1 <img src="../images/lteq12.gif"> <I>j</I> <img src="../images/lteq12.gif"> <I>n</I>.<P>
<I><B>c.</I></B>     Prove that the family of odd-even sorting networks is indeed a family of sorting networks.<P>
<a name="0929_1949">28-2 Batcher's odd-even merging network<a name="0929_1949"><P>
<a name="0929_1941"><a name="0929_1942"><a name="0929_1943"><a name="0929_1944">In Section 28.4, we saw how to construct a merging network based on bitonic sorting. In this problem, we shall construct an <I><B>odd-even merging network</I></B>. We assume that <I>n</I> is an exact power of 2, and we wish to merge the sorted sequence of elements on lines <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"> with those on lines <img src="../images/lftwdchv.gif"><I>a<SUB>n</I>+1</SUB>, <I>a<SUB>n</I>+2</SUB>, . . . , <I>a</I><SUB>2<I>n</I></SUB><img src="../images/wdrtchv.gif">. We recursively construct two odd-even merging networks that merge sorted subsequences in parallel. The first merges the sequence on lines <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"> with the sequence on lines <img src="../images/lftwdchv.gif"><I>a<SUB>n</I>+1</SUB>, <I>a<SUB>n</I>+3</SUB>, . . . , <I>a</I><SUB>2<I>n-</I>1</SUB><img src="../images/wdrtchv.gif"> (the odd elements). The second merges <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"> with <img src="../images/lftwdchv.gif"><I>a<SUB>n</I>+2</SUB>, <I>a<SUB>n</I>+4</SUB>, . . . , <I>a</I><SUB>2<I>n</I></SUB><img src="../images/wdrtchv.gif"> (the even elements). To combine the two sorted subsequences, we put a comparator between <I>a</I><SUB>2<I>i</I>-1</SUB> and <I>a</I><SUB>2<I>i</I></SUB> for <I>i</I> = 1, 2, . . . , <I>n</I>.<P>
<I><B>a.</I></B>     Draw a 2<I>n</I>-input merging network for<I> n </I>= 4.<P>
<img src="651_a.gif"><P>
<h4><a name="0929_194a">Figure 28.13 An odd-even sorting network on 8 inputs.<a name="0929_194a"></sub></sup></h4><P>
<img src="652_a.gif"><P>
<h4><a name="0929_194b">Figure 28.14 Permutation networks. (a) The permutation network P<SUB>2</SUB>, which consists of a single switch that can be set in either of the two ways shown. (b) The recursive construction of P<SUB>8</SUB> from 8 switches and two P<SUB>4</SUB>'s. The switches and P<SUB>4</SUB>'s are set to realize the permutation <img src="../images/piuc.gif"> = <img src="../images/lftwdchv.gif">4, 7, 3, 5, 1, 6, 8, 2<img src="../images/wdrtchv.gif">.<a name="0929_194b"></sub></sup></h4><P>
<I><B>b.</I></B>     Use the zero-one principle to prove that any 2<I>n</I>-input odd-even merging network is indeed a merging network.<P>
<I><B>c.</I></B>     What is the depth of a 2<I>n</I>-input odd-even merging network? What is its size?<P>
<a name="0929_194c">28-3 Permutation networks<a name="0929_194c"><P>
<a name="0929_1945"><a name="0929_1946">A <I><B>permutation network</I></B> on<I> n </I>inputs and <I>n</I> outputs has switches that allow it to connect its inputs to its outputs according to any of the <I>n</I>! possible permutations. Figure 28.14(a) shows the 2-input, 2-output permutation network <I>P</I><SUB>2</SUB>, which consists of a single switch that can be set either to feed its inputs straight through to its outputs or to cross them.<P>
<I><B>a.</I></B>     Argue that if we replace each comparator in a sorting network with the switch of Figure 28.14(a), the resulting network is a permutation network. That is, for any permutation <img src="../images/piuc.gif">, there is a way to set the switches in the network so that input <I>i</I> is connected to output <img src="../images/piuc.gif">(<I>i</I>).<P>
Figure 28.14(b) shows the recursive construction of an 8-input, 8-output permutation network <I>P</I><SUB>8</SUB> that uses two copies of <I>P</I><SUB>4</SUB> and 8 switches. The switches have been set to realize the permutation <img src="../images/piuc.gif"> = <img src="../images/lftwdchv.gif">4, 7, 3, 5, 1, 6, 8, 2<img src="../images/wdrtchv.gif">, which requires (recursively) that the top <I>P</I><SUB>4</SUB> realize <img src="../images/lftwdchv.gif">4, 2, 3, 1<img src="../images/wdrtchv.gif"> and the bottom <I>P</I><SUB>4</SUB> realize <img src="../images/lftwdchv.gif">2, 3, 1, 4<img src="../images/wdrtchv.gif">.<P>
<I><B>b.</I></B>     Show how to realize the permutation <img src="../images/lftwdchv.gif">5, 3, 4, 6, 1, 8, 2, 7<img src="../images/wdrtchv.gif"> on <I>P</I><SUB>8</SUB> by drawing the switch settings and the permutations performed by the two <I>P</I><SUB>4</SUB>'s.<P>
Let<I> n </I>be an exact power of 2. Define <I>P<SUB>n</I></SUB> recursively in terms of two <I>P<SUB>n</I>/2</SUB><FONT FACE="CG Times (W1)" SIZE=1>'</FONT>s in a manner similar to the way we defined <I>P</I><SUB>8</SUB>.<P>
<I><B>c.</I></B>      Describe an <I>O</I>(<I>n</I>)-time (ordinary random-access machine) algorithm that sets the <I>n</I> switches connected to the inputs and outputs of <I>P<SUB>n</I></SUB> and specifies the permutations that must be realized by each <I>P<SUB>n</I>/2</SUB> in order to accomplish any given <I>n</I>-element permutation. Prove that your algorithm is correct.<P>
<I><B>d.</I></B>     What are the depth and size of <I>P<SUB>n</I></SUB>? How long does it take on an ordinary random-access machine to compute all switch settings, including those within the <I>P<SUB>n</I>/2</SUB><FONT FACE="CG Times (W1)" SIZE=1>'</FONT>s?<P>
<I><B>e.</I></B>     Argue that for <I>n</I> &gt; 2, any permutation network--not just <I>P<SUB>n</I></SUB>--must realize some permutation by two distinct combinations of switch settings.<P>
<P>







<h1>Chapter notes</h1><P>
Knuth [123] contains a discussion of sorting networks and charts their history. They apparently were first explored in 1954 by P. N. Armstrong, R. J. Nelson, and D. J. O'Connor. In the early 1960's, K. E. Batcher discovered the first network capable of merging two sequences of <I>n</I> numbers in <I>O</I>(lg <I>n</I>) time. He used odd-even merging (see Problem 28-2), and he also showed how this technique could be used to sort<I> n </I>numbers in <I>O</I>(lg<SUP>2</SUP> <I>n</I>) time. Shortly afterwards, he discovered an <I>O</I>(lg <I>n</I>)-depth bitonic sorter similar to the one presented in Section 28.3. Knuth attributes the zero-one principle to W. G. Bouricius (1954), who proved it in the context of decision trees.<P>
<a name="092a_1947"><a name="092a_1948">For a long time, the question remained open as to whether a sorting network with depth <I>O</I>(lg <I>n</I>) exists. In 1983, the answer was shown to be a somewhat unsatisfying yes. The AKS sorting network (named after its developers, Ajtai, Koml&oacute;s, and Szemer&eacute;di [8]) can sort <I>n</I> numbers in depth <I>O</I>(lg <I>n</I>) using <I>O</I>(<I>n</I> lg <I>n</I>) comparators. Unfortunately, the constants hidden by the <I>O</I>-notation are quite large (many, many thousands), and thus it cannot be considered practical.<P>
<P>


<P>
<P>
<center>Go to <a href="chap29.htm">Chapter 29</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>


</BODY></HTML>