Content deleted Content added
FenixFeather (talk | contribs) →0-1 principle: A little late for this, but if you do manage to find a reliable source explaining this, I'm sure it could be integrated into the article. |
|||
Line 584:
:{{Reply|Smjg}} A little late for this, but if you do manage to find a reliable source explaining this, I'm sure it could be integrated into the article. – [[User:FenixFeather|<font color="SlateBlue">'''''FenixFeather'''''</font>]] <sup>[[User_talk:FenixFeather|<font color="SlateBlue">(talk)]]</font></sup><sup>[[Special:Contributions/FenixFeather|<font color="SlateBlue">(Contribs)]]</font></sup> 04:36, 11 April 2014 (UTC)
:: That's kinda obvious.... — [[User:Smjg|Smjg]] ([[User talk:Smjg|talk]]) 14:52, 12 April 2014 (UTC)
For what it's worth, I've just tried searching again and found this: [http://dcg.ethz.ch/lectures/podc_allstars/lecture/chapter4_2on1.pdf]
: "The most interesting proof uses the so-called 0-1 Sorting Lemma. It allows us to restrict our attention to an input of 0’s and 1’s only, and works for any “oblivious comparison-exchange” algorithm. (Oblivious means: Whether you exchange two values must only depend on the relative order of the two values, and not on anything else.)"
: "Whenever the algorithm compares a pair of 1’s or 0’s, it is not important whether it exchanges the values or not, so we may simply assume that it does the same as on the input x."
What ''is'' important, however, is whether the algorithm has any conditional behaviour, other than just the swapping of the elements, based on the result of the comparison.
Maybe "oblivious comparison-exchange" was the phrasing my lecturer used. I guess that this phrase means an operation of the form "if A > B, swap A and B", and the essence is that the data is in a [[black box]] and the algorithm has access to it only by this operation (which returns no value, hence "oblivious") plus knowledge of the length of the array.
This means that, for a given algorithm and input size, the sequence of oblivious comparison-exchanges is a constant. So what we really have is an algorithm for building a [[sorting network]] and then applying it. That said, on a given pair A and B, it can equally be either "if A > B, swap A and B" or "if B > A, swap B and A". So if you don't consider [[sorting networks]] to be allowed to have reverse comparators, then we have a generalisation of the sorting network 0-1 principle to a wider class of algorithms. Otherwise, it doesn't really generalise the principle at all.
Maybe what we can still say is that the 0-1 principle can be used to prove the correctness of ''some'' sorting algorithms. I'll see what I can come up with.... — [[User:Smjg|Smjg]] ([[User talk:Smjg|talk]]) 14:52, 12 April 2014 (UTC)
== Sorting networks section still needs work ==
| |||