[Solved]: How do I tell if a comparison network sorts?

Problem Detail: 

I am presented with a comparison network. How can I determine if the comparison network is a sorting network? In the image below there is an example of a selection sort and insertion sort network. The intent is to have a comparison network and sort numeric values. If I test 2^n values in this case 2^8. This is a lot of work|non-efficient way to test it. I'm looking for a mathematical model/proof to verify this is a valid sorting network.

Asked By : spicyramen

Answered By : D.W.

In general, verifying whether a particular comparison network is indeed a correct sorting network is a Co-NP complete problem. If you want to check by testing, then you need to try exponentially many tests.

In particular, there exist sorting networks that sort all but a single value correctly, so you can't hope to test whether the network is correct or not simply by feeding it a few inputs.

One standard method is to test whether it correctly sorts all $2^n$ inputs that are composed solely of zeros and ones. If it does, then it turns out that it will sort all inputs (even ones that aren't limited to zeros and ones). However, this requires exponentially many tests. Moreover, the number of tests cannot be reduced significantly: for zero-one inputs, it is possible to prove that at least $2^n-n-1$ tests are needed, to very that the sorting network is correct.

Alternatively, one can use tests where the inputs are permutations of $1,2,\dots,n$. This reduces the number of tests needed somewhat, but you still need exponentially many tests. In particular, $C(n, \lfloor n/2 \rfloor)-1$ tests are necessary and sufficient.

For proofs of these facts, see the following papers:

On the Computational Complexity of Optimal Sorting Network Verification. Ian Parberry. Parle'91 Parallel Architectures and Languages Europe, 1991.

Bounds on the size of test sets for sorting and related networks. Moon Jung Chung and B. Ravikumar. Discrete Mathematics, vol 81, pp.1--9, April 1990.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44748

 Ask a Question

 Download Related Notes/Documents