27.2 The zero-one principle

| < Day Day Up > |

## 27.2 The zero-one principle

The zero-one principle 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.

The proof of the zero-one principle relies on the notion of a monotonically increasing function (Section 3.2).

Lemma 27.1

If a comparison network transforms the input sequence a = 〈a1, a2,...,an〉 into the output sequence b = 〈b1, b2,...,bn〉, then for any monotonically increasing function f, the network transforms the input sequence f (a) = 〈f(a1), f(a2),...,f(an)〉 into the output sequence f(b) = 〈f(b1), f(b2),...,f(bn)〉.

Proof We shall first prove the claim that if f is a monotonically increasing function, then a single comparator with inputs f(x) and f(y) produces outputs f(min(x, y)) and f(max(x, y)). We then use induction to prove the lemma.

To prove the claim, consider a comparator whose input values are x and y. The upper output of the comparator is min(x, y) and the lower output is max(x, y). Suppose we now apply f(x) and f(y) to the inputs of the comparator, as is shown in Figure 27.4. The operation of the comparator yields the value min(f(x), f(y)) on the upper output and the value max(f(x), f(y)) on the lower output. Since f is monotonically increasing, x ≤ y implies f(x) ≤ f(y). Consequently, we have the identities

min(f(x), f(y)) | = | f(max(x, y)),
max(f(x), f(y)) | = | f(min(x, y)).

Figure 27.4: The operation of the comparator in the proof of Lemma 27.1. The function f is monotonically increasing.

Thus, the comparator produces the values f(min(x, y)) and f(max(x, y)) when f(x) and f(y) are its inputs, which completes the proof of the claim.

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 ai when the input sequence a is applied to the network, then it assumes the value f(ai) when the input sequence f(a) is applied. Because the output wires are included in this statement, proving it will prove the lemma.

For the basis, consider a wire at depth 0, that is, an input wire ai. The result follows trivially: when f(a) is applied to the network, the input wire carries f(ai). For the inductive step, consider a wire at depth d, where d ≥ 1. The wire is the output of a comparator at depth d, and the input wires to this comparator are at a depth strictly less than d. By the inductive hypothesis, therefore, if the input wires to the comparator carry values ai and aj when the input sequence a is applied, then they carry f(ai) and f(aj) when the input sequence f(a) is applied. By our earlier claim, the output wires of this comparator then carry f(min(ai, aj)) and f(max(ai, aj)). Since they carry min(ai, aj) and max(ai, aj) when the input sequence is a, the lemma is proved.

As an example of the application of Lemma 27.1, Figure 27.5(b) shows the sorting network from Figure 27.2 (repeated in Figure 27.5(a)) with the monotonically increasing function f(x) = ⌈x/2⌉ applied to the inputs. The value on every wire is f applied to the value on the same wire in Figure 27.2.

Figure 27.5: (a) The sorting network from Figure 27.2 with input sequence 〈9, 5, 2, 6〉. (b) The same sorting network with the monotonically increasing function f(x) = f(⌈x/2⌉) applied to the inputs. Each wire in this network has the value of f applied to the value on the corresponding wire in (a).

When a comparison network is a sorting network, Lemma 27.1 allows us to prove the following remarkable result.

Theorem 27.2: (Zero-one principle)

If a comparison network with n inputs sorts all 2n possible sequences of 0's and 1's correctly, then it sorts all sequences of arbitrary numbers correctly.

Proof 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 〈a1, a2,...,an〉 containing elements ai and aj such that ai < aj, but the network places aj before ai in the output sequence. We define a monotonically increasing function f as

Since the network places aj before ai in the output sequence when 〈a1, a2,...,an〉 is input, it follows from Lemma 27.1 that it places f(aj) before f(ai) in the output sequence when 〈f(a1), f(a2),...,f(an)〉 is input. But since f(aj) = 1 and f(ai) = 0, we obtain the contradiction that the network fails to sort the zero-one sequence 〈f(a1), f(a2),...,f(an)〉 correctly.

Exercises 27.2-1

Prove that applying a monotonically increasing function to a sorted sequence produces a sorted sequence.

Exercises 27.2-2

Prove that a comparison network with n inputs correctly sorts the input sequence 〈n, n - 1,..., 1〉 if and only if it correctly sorts the n - 1 zero-one sequences 〈1, 0, 0,..., 0, 0〉, 〈1, 1, 0,..., 0, 0〉,..., 〈1, 1, 1,..., 1, 0〉.

Exercises 27.2-3

Use the zero-one principle to prove that the comparison network shown in Figure 27.6 is a sorting network.

Figure 27.6: A sorting network for sorting 4 numbers.

Exercises 27.2-4

State and prove an analog of the zero-one principle for a decision-tree model. (Hint: Be sure to handle equality properly.)

Exercises 27.2-5

Prove that an n-input sorting network must contain at least one comparator between the ith and (i + 1)st lines for all i = 1, 2,..., n - 1.

| < Day Day Up > |