4
$\begingroup$

When dealing with sorting networks, we can check the validity of a sorting network with only $2^n$ sequences of $0$ and $1$ (where $n$ is the size of the collection to sort) thanks to the zero-one principle:

The zero-one principle states that, if a sorting network can correctly sort all $2^n$ sequences of zeros and ones, then it is also valid for arbitrary ordered inputs.

I have used this principle to prove that my sorting networks worked. However, I also wanted to check whether some of them were stable or not: in order to do so, I tried to feed pairs of $(0, index)$ and $(1, index)$ to the networks instead of simple $0$ and $1$ and checked whether the indices of elements with the same values were still in the correct order after the sort (of course, the sequences were sorted based only on the first value of the pair). It was sufficient to prove that my sorting networks weren't stable since the algorithm was able to find at least one sequence that wasn't stably sorted per network.

However, even if every sequence was stably sorted, I still wouldn't be sure whether the sorting networks are stable or not without answering this question: can the zero-one principle be used to prove the stability of a sorting network?

$\endgroup$
  • 2
    $\begingroup$ Did you try proving that it does? Did you try finding a counterexample? $\endgroup$ – Yuval Filmus Jan 5 '16 at 12:52
  • 1
    $\begingroup$ See also cs.stackexchange.com/q/44748/755 (not a dup). You might want to check whether any of the references cited there discuss verification of stability. You might also check out hoytech.github.io/sorting-networks (e.g., slides 27-28). $\endgroup$ – D.W. Jan 5 '16 at 17:47
  • $\begingroup$ @YuvalFilmus To be honest, no, I didn't try to prove it. I'm kind of worthless at proving things but I still prefer to ship code that has more or less been proven to work. I did try to find counterexamples but didn't find any. $\endgroup$ – Morwenn Jan 6 '16 at 22:54
2
$\begingroup$

You can use a $0/1/2$ principle, in which the inputs are $\{0,1,2\}$, and $1$-inputs are also annotated by their indices. The network should sort the input successfully, maintaining the order of the $1$-entries. This is clearly a necessary condition, and it's not too hard to show that it is sufficient.

That doesn't quite answer your own question, though I conjecture that your criterion isn't sufficient. All one needs to do in order to prove my conjecture is to give a sorting network satisfying your condition but not mine. You can try looking for such a network using a computer. If you can find no such network, perhaps your criterion does work after all.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.