📄 chap28.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 28: SORTING NETWORKS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap29.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="partvii.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="091b_1913">CHAPTER 28: SORTING NETWORKS<a name="091b_1913"></h1><P>
<a name="091b_1912">In Part II, we examined sorting algorithms for serial computers (random-access machines, or RAM's) that allow only one operation to be executed at a time. In this chapter, we investigate sorting algorithms based on a comparison network model of computation in which many comparison operations can be performed simultaneously.<P>
Comparison networks differ from RAM's in two important respects. First, they can only perform comparisons. Thus, an algorithm such as counting sort (see Section 9.2) cannot be implemented on a comparison network. Second, unlike the RAM model, in which operations occur serially--that is, one after another--operations in a comparison network may occur at the same time, or "in parallel." As we shall see, this characteristic allows the construction of comparison networks that sort <I>n</I> values in sublinear time.<P>
We begin in Section 28.1 by defining comparison networks and sorting networks. We also give a natural definition for the "running time" of a comparison network in terms of the depth of the network. Section 28.2 proves the "zero-one principle," which greatly eases the task of analyzing the correctness of sorting networks.<P>
The efficient sorting network that we shall design is essentially a parallel version of the merge-sort algorithm from Section 1.3.1. Our construction will have three steps. Section 28.3 presents the design of a "bitonic" sorter that will be our basic building block. We modify the bitonic sorter slightly in Section 28.4 to produce a merging network that can merge two sorted sequences into one sorted sequence. Finally, in Section 28.5, we assemble these merging networks into a sorting network that can sort <I>n</I> values in <I>O</I>(lg<SUP>2</SUP> <I>n</I>)<I> </I>time.<P>
<h1><a name="091d_1920">28.1 Comparison networks<a name="091d_1920"></h1><P>
<a name="091d_1913"><a name="091d_1914"><a name="091d_1915"><a name="091d_1916">Sorting networks are comparison networks that always sort their inputs, so it makes sense to begin our discussion with comparison networks and their characteristics. A comparison network is comprised solely of wires and comparators. A <I><B>comparator</I></B>, shown in Figure 28.1 (a), is a device with two inputs, <I>x</I> and <I>y</I>, and two outputs, <I>x</I>' and <I>y</I>', that performs the following function:<P>
<img src="635_a.gif"><P>
<h4><a name="091d_1921">Figure 28.1 (a) A comparator with inputs x and y and outputs x' and y'. (b) The same comparator, drawn as a single vertical line. Inputs x = 7, y = 3 and outputs x' = 3, y' = 7 are shown.<a name="091d_1921"></sub></sup></h4><P>
<pre><I>x</I>' = min(<I>x, y</I>) ,</sub></sup></pre><P>
<pre><I>y</I>' = max(<I>x, y</I>) .</sub></sup></pre><P>
Because the pictorial representation of a comparator in Figure 28.1 (a) is too bulky for our purposes, we shall adopt the convention of drawing comparators as single vertical lines, as shown in Figure 28.1(b). Inputs appear on the left and outputs on the right, with the smaller input value appearing on the top output and the larger input value appearing on the bottom output. We can thus think of a comparator as sorting its two inputs.<P>
We shall assume that each comparator operates in <I>O</I>(1) time. In other words, we assume that the time between the appearance of the input values <I>x</I> and <I>y</I> and the production of the output values <I>x</I>' and <I>y</I>' is a constant.<P>
<a name="091d_1917"><a name="091d_1918"><a name="091d_1919"><a name="091d_191a"><a name="091d_191b"><a name="091d_191c">A <I><B>wire</I></B> 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. Throughout this chapter, we shall assume that a comparison network contains <I>n</I> <I><B>input wires</I></B><I> a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB>, through which the values to be sorted enter the network, and <I>n</I> <I><B>output wires</I></B> <I>b</I><SUB>1</SUB>, <I>b</I><SUB>2</SUB>, . . . , <I>b<SUB>n</I></SUB>, which produce the results computed by the network. Also, we shall speak of the <I><B>input sequence</I></B> <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"> and the <I><B>output sequence</I></B> <img src="../images/lftwdchv.gif"><I>b</I><SUB>1</SUB>,<I>b</I><SUB>2, . . . ,</SUB><I>b<SUB>n</I></SUB><img src="../images/wdrtchv.gif">, referring to the values on the input and output wires. That is, we use the same name for both a wire and the value it carries. Our intention will always be clear from the context.<P>
Figure 28.2 shows a <I><B>comparison network</I></B>, which is a set of comparators interconnected by wires. We draw a comparison network on <I>n</I> inputs as a collection of <I>n</I> horizontal <I><B>lines</I></B> with comparators stretched vertically. Note that a line does <I>not</I> represent a single wire, but rather a sequence of distinct wires connecting various comparators. The top line in Figure 28.2, for example, represents three wires: input wire <I>a</I><SUB>1</SUB>, which connects to an input of comparator <I>A</I>; a wire connecting the top output of comparator <I>A</I> to an input of comparator <I>C</I>; and output wire <I>b</I><SUB>1</SUB>, which comes from the top output of comparator <I>C</I>. Each comparator input is connected to a wire that is either one of the network's <I>n</I> input wires <I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, . . . , <I>a<SUB>n</I></SUB> or is connected to the output of another comparator. Similarly, each comparator output is connected to a wire that is either one of the network's <I>n</I> output wires <I>b</I><SUB>1</SUB>, <I>b</I><SUB>2</SUB>, . . . , <I>b<SUB>n</I></SUB> or is connected to the input of another comparator. The main requirement for interconnecting comparators is that the graph of interconnections must be acyclic: if we trace a path from the output of a given comparator to the input of another to output to input, etc., the path we trace must never cycle back on itself and go through the same comparator twice. Thus, as in Figure 28.2, we can draw a comparison network with network inputs on the left and network outputs on the right; data move through the network from left to right.<P>
<img src="636_a.gif"><P>
<h4><a name="091d_1922">Figure 28.2 (a) A 4-input, 4-output comparison network, which is in fact a sorting network. At time 0, the input values shown appear on the four input wires. (b) At time 1, the values shown appear on the outputs of comparators A and B, which are at depth l. (c) At time 2, the values shown appear on the outputs of comparators C and D, at depth 2. Output wires b<SUB>1</SUB> and b<SUB>4</SUB> now have their final values, but output wires b<SUB>2</SUB> and b<SUB>3</SUB> do not. (d) At time 3, the values shown appear on the outputs of comparator E, at depth 3. Output wires b<SUB>2</SUB> and b<SUB>3</SUB> now have their final values.<a name="091d_1922"></sub></sup></h4><P>
Each comparator produces its output values only when both of its input values are available to it. In Figure 28.2(a), for example, suppose that the sequence <img src="../images/lftwdchv.gif">9, 5, 2, 6<img src="../images/wdrtchv.gif"> appears on the input wires at time 0. At time 0, then, only comparators <I>A</I> and <I>B</I> have all their input values available. Assuming that each comparator requires one time unit to compute its output values, comparators <I>A</I> and <I>B</I> produce their outputs at time 1; the resulting values are shown in Figure 28.2(b). Note that comparators <I>A</I> and <I>B</I> produce their values at the same time, or "in parallel." Now, at time 1, comparators <I>C </I>and <I>D</I>, but not <I>E</I>, have all their input values available. One time unit later, at time 2, they produce their outputs, as shown in Figure 28.2(c). Comparators <I>C</I> and <I>D</I> operate in parallel as well. The top output of comparator <I>C</I> and the bottom output of comparator <I>D</I> connect to output wires <I>b</I><SUB>1</SUB> and <I>b</I><SUB>4</SUB>, respectively, of the comparison network, and these network output wires therefore carry their final values at time 2. Meanwhile, at time 2, comparator <I>E</I> has its inputs available, and Figure 28.2(d) shows that it produces its output values at time 3. These values are carried on network output wires <I>b</I><SUB>2</SUB> and <I>b</I><SUB>3</SUB>, and the output sequence <img src="../images/lftwdchv.gif">2, 5, 6, 9<img src="../images/wdrtchv.gif"> is now complete.<P>
<a name="091d_191d"><a name="091d_191e">Under the assumption that each comparator takes unit time, we can define the "running time" of a comparison network, that is, the time it takes for all the output wires to receive their values once the input wires receive theirs. Informally, this time is the largest number of comparators that any input element can pass through as it travels from an input wire to an output wire. More formally, we define the <I><B>depth</I></B> of a wire as follows. An input wire of a comparison network has depth 0. Now, if a comparator has two input wires with depths <I>d<SUB>x</I></SUB> and <I>d<SUB>y</I></SUB>, then its output wires have depth max(<I>d<SUB>x</I></SUB>, <I>d<SUB>y</I></SUB>) + 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. Figure 28.2 shows comparator depths. The depth of a comparison network is the maximum depth of an output wire or, equivalently, the maximum depth of a comparator. The comparison network of Figure 28.2, for example, has depth 3 because comparator <I>E</I> has depth 3. If each comparator takes one time unit to produce its output value, and if network inputs appear at time 0, a comparator at depth <I>d</I> produces its outputs at time <I>d</I>; the depth of the network therefore equals the time for the network to produce values at all of its output wires.<P>
<a name="091d_191f">A <I><B>sorting network</I></B> is a comparison network for which the output sequence is monotonically increasing (that is, <I>b</I><SUB>1</SUB> <img src="../images/lteq12.gif"> <I>b</I><SUB>2</SUB> <img src="../images/lteq12.gif"> . . . <img src="../images/lteq12.gif"> <I>b<SUB>n</I></SUB>) for <I>every</I> input sequence. Of course, not every comparison network is a sorting network, but the network of Figure 28.2 is. To see why, observe that after time 1, the minimum of the four input values has been produced by either the top output of comparator <I>A</I> or the top output of comparator <I>B</I>. After time 2, therefore, it must be on the top output of comparator <I>C</I>. A symmetrical argument shows that after time 2, the maximum of the four input values has been produced by the bottom output of comparator <I>D</I>. All that remains is for comparator <I>E </I>to ensure that the middle two values occupy their correct output positions, which happens at time 3.<P>
A comparison network is like a procedure in that it specifies how comparisons are to occur, but it is unlike a procedure in that its physical size depends on the number of inputs and outputs. Therefore, we shall actually be describing "families" of comparison networks. For example, the goal of this chapter is to develop a family <FONT FACE="Courier New" SIZE=2>SORTER</FONT> of efficient sorting networks. We specify a given network within a family by the family name and the number of inputs (which equals the number of outputs). For example, the <I>n</I>-input, <I>n</I>-output sorting network in the family <FONT FACE="Courier New" SIZE=2>SORTER</FONT> is named <FONT FACE="Courier New" SIZE=2>SORTER</FONT>[<I>n</I>].<P>
<img src="638_a.gif"><P>
<h4><a name="091d_1923">Figure 28.3 A sorting network based on insertion sort for use in Exercise 28.1-6.<a name="091d_1923"></sub></sup></h4><P>
<h2><a name="091e_1925">Exercises<a name="091e_1925"></h2><P>
<a name="091e_1926">28.1-1<a name="091e_1926"><P>
Show the values that appear on all the wires of the network of Figure 28.2 when it is given the input sequence <img src="../images/lftwdchv.gif">9, 6, 5, 2<img src="../images/wdrtchv.gif">.<P>
<a name="091e_1927">28.1-2<a name="091e_1927"><P>
Let <I>n</I> be an exact power of 2. Show how to construct an <I>n</I>-input, <I>n</I>-output comparison network of depth lg <I>n</I> in which the top output wire always carries the minimum input value and the bottom output wire always carries the maximum input value.<P>
<a name="091e_1928">28.1-3<a name="091e_1928"><P>
<a name="091e_1920"><a name="091e_1921">Professor Nielsen claims that if we add a comparator anywhere in a sorting network, the resulting network also sorts. Show that the professor is mistaken by adding a comparator to the network of Figure 28.2 in such a way that the resulting network does not sort every input permutation.<P>
<a name="091e_1929">28.1-4<a name="091e_1929"><P>
<a name="091e_1922">Prove that any sorting network on <I>n</I> inputs has depth at least lg <I>n</I>.<P>
<a name="091e_192a">28.1-5<a name="091e_192a"><P>
Prove that the number of comparators in any sorting network is at least <img src="../images/omega12.gif">(<I>n</I> lg <I>n</I>).<P>
<a name="091e_192b">28.1-6<a name="091e_192b"><P>
<a name="091e_1923"><a name="091e_1924">Consider the comparison network shown in Figure 28.3. Prove that it is in fact a sorting network, and describe how its structure is related to that of insertion sort (Section 1.1).<P>
<a name="091e_192c">28.1-7<a name="091e_192c"><P>
We can represent an <I>n</I>-input comparison network with <I>c</I> comparators as a list of <I>c</I> pairs of integers in the range from 1 to <I>n</I>. If two pairs contain an integer in common, the order of the corresponding comparators in the network is determined by the order of the pairs in the list. Given this representation, describe an<I> O</I>(<I>n</I>+<I>c</I>)-time (serial) algorithm for determining the depth of a comparison network.<P>
<a name="091e_192d">28.1-8<a name="091e_192d"><P>
Suppose that in addition to the standard kind of comparator, we introduce an "upside-down" comparator that produces its minimum output on the bottom wire and its maximum output on the top wire. Show how to convert any sorting network that uses a total of <I>c</I> standard and upside-down comparators to one that uses <I>c</I> standard ones. Prove that your conversion method is correct.<P>
<P>
<P>
<h1><a name="091f_1926">28.2 The zero-one principle<a name="091f_1926"></h1><P>
<a name="091f_1925">The <I><B>zero-one principle</I></B> says that 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.) As we construct sorting networks and other comparison networks, the zero-one principle will allow us to focus on their operation for input sequences consisting solely of 0's and 1's. Once we have constructed a sorting network and proved that it can sort all zero-one sequences, we shall appeal to the zero-one principle to show that it properly sorts sequences of arbitrary values.<P>
The proof of the zero-one principle relies on the notion of a monotonically increasing function (Section 2.2).<P>
<a name="091f_1927">Lemma 28.1<a name="091f_1927"><P>
If a comparison network transforms the input sequence <I>a</I> = <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"> into the output sequence <I>b</I> = <img src="../images/lftwdchv.gif"><I>b</I><SUB>1</SUB>, <I>b</I><SUB>2</SUB>, . . . , <I>b<SUB>n</I></SUB><img src="../images/wdrtchv.gif">, then for any monotonically increasing function <I>f</I>, the network transforms the input sequence <I>f</I>(<I>a</I>) = <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"> into the output sequence<I> f</I>(<I>b</I>) = <img src="../images/lftwdchv.gif"><I>f</I>(<I>b</I><SUB>1</SUB>), <I>f</I>(<I>b</I><SUB>2</SUB>), . . . , <I>f</I>(<I>b<SUB>n</I></SUB>)<img src="../images/wdrtchv.gif">.<P>
<I><B>Proof </I></B>We shall first prove the claim that if <I>f</I> is a monotonically increasing function, then a single comparator with inputs<I> f</I>(<I>x</I>) and <I>f</I>(<I>y</I>) produces outputs <I>f</I>(min(<I>x,y</I>)) and <I>f</I>(max(<I>x,y</I>)). We shall then use induction to prove the lemma.<P>
To prove the claim, consider a comparator whose input values are <I>x</I> and <I>y</I>. The upper output of the comparator is min(<I>x,y</I>) and the lower output is max(<I>x,y</I>). Suppose we now apply<I> f</I>(<I>x</I>) and<I> f</I>(<I>y</I>) to the inputs of the comparator, as is shown in Figure 28.4. The operation of the comparator yields the value min(<I>f</I>(<I>x</I>), <I>f</I>(<I>y</I>)) on the upper output and the value max(<I>f</I>(<I>x</I>), <I>f</I>(<I>y</I>)) on the lower output. Since<I> f</I> is monotonically increasing, <I>x</I> <img src="../images/lteq12.gif"> <I>y</I> implies <I>f</I>(<I>x</I>) <img src="../images/lteq12.gif"> <I>f</I>(<I>y</I>). Consequently, we have the identities<P>
<pre>min(<I>f</I>(<I>x</I>), <I>f</I>(<I>y</I>)) = <I>f</I>(min(<I>x,y</I>)) ,</sub></sup></pre><P>
<pre>max(<I>f</I>(<I>x</I>), <I>f</I>(<I>y</I>)) = <I>f</I>(max(<I>x,y</I>)) .</sub></sup></pre><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -