Sorting networks

The 0-1-principle

 German version  up

An indispensable tool for the proof of correctness of sorting networks is the 0-1-principle [Knu 73]. The 0-1-principle states the following:

Theorem:  (0-1-principle)

If a sorting network sorts every sequence of 0's and 1's, then it sorts every arbitrary sequence of values.

The proof of the 0-1-principle is not very difficult. However, it is quite helpful to have some definitions and lemmas ready.

 

Preliminaries

Definition:  Let A and B be ordered sets. A mapping f : A arrow B is called monotonic if for all a1, a2 element A

a1<=a2   implies   f(a1)<=f(a2)

Lemma:  Let f : A arrow B be a monotonic mapping. Then the following holds for all a1, a2 element A :

f(min(a1, a2))  =  min(f(a1), f(a2))

Proof:  Let a1<=a2 and thus f(a1)<=f(a2). Then

min(a1, a2) = a1   and   min(f(a1), f(a2)) = f(a1)

This implies

f(min(a1, a2))  =  f(a1)  =  min(f(a1), f(a2))

Similarly, if a2<=a1 and therefore f(a2)<=f(a1), we have

f(min(a1, a2))  =  f(a2)  =  min(f(a1), f(a2))

An analogous property holds for the max-function.

Definition:  Let f : A arrow B be a mapping. The extension of f to finite sequences a = a0, ..., an-1,  ai element A is defined as follows:

f(a0, ..., an-1)  =  f(a0), ..., f(an-1) ,   i.e.

f(a)i  =  f(ai)

Lemma:  Let f be a monotonic mapping and N a comparator network. Then N and f commutate, i.e. for every finite sequence a = a0, ..., an-1 the following holds:

N( f(a) )  =  f( N(a) )

In other words: a monotonic mapping f can be applied to the input sequence of comparator network N or to the output sequence, the result is the same.

Proof:  For a single comparator [i:j] the following holds (see definition of comparator):

[i:j]( f(a) )i  =  [i:j]( f(a0), ..., f(an-1) )i  =  min( f(ai), f(aj) )

  =  f( min(ai, aj) )  =  f( [i:j](a)i )  =  f( [i:j](a) )i

This means that the ith element is the same regardless of the order of application of f and [i:j]. The same can be shown for the jth element and for all other elements. Therefore

[i:j]( f(a) )  =  f( [i:j](a) )

For an arbitrary comparator network N (which is a composition of comparators) and a monotonic mapping f we have therefore

N( f(a) )  =  f( N(a) )

 

Proof of the 0-1-principle

Theorem:  (0-1-principle)

Let N be a comparator network. If every 0-1-sequence is sorted by N, then every arbitrary sequence is sorted by N.

Proof:  Suppose a with ai element A is an arbitrary sequence which is not sorted by N. This means N(a) = b is unsorted, i.e. there is a position k such that bk > bk+1.

Now define a mapping f : A arrow {0, 1} as follows. For all c element A let

 f(c)  =   open brace
0       if  c < bk
1    if  c>=bk

Obviously, f is monotonic. Moreover we have:

f(bk) = 1   and   f(bk+1) = 0

i.e. f(b) = f(N(a)) is unsorted.

This means that N(f(a)) is unsorted or, in other words, that the 0-1-sequence f(a) is not sorted by the comparator network N.

We have shown that, if there is an arbitrary sequence a that is not sorted by N, then there is a 0-1-sequence f(a) that is not sorted by N.

Equivalently, if there is no 0-1-sequence that is not sorted by N, then there can be no sequence a whatsoever that is not sorted by N.

Equivalently again, if all 0-1-sequences are sorted by N, then all arbitrary sequences are sorted by N.

 

References

[Knu 73]D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)

 

 

up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 02.02.1997   Updated: 24.02.2011
Valid HTML 4.01 Transitional