Content deleted Content added
m Signing comment by Nileshrathi01 - "→Adding explanation for in-place sort: new section" |
→0-1 principle: new section |
||
Line 568:
There should be a section explaining what an in place sort is just like there is a section for explaining stability of sorting <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Nileshrathi01|Nileshrathi01]] ([[User talk:Nileshrathi01|talk]] • [[Special:Contributions/Nileshrathi01|contribs]]) 14:07, 5 October 2013 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
== 0-1 principle ==
From my university studies I recall there being something called the 0-1 principle. The statement is something like this:
"If an oblivious comparison-based sorting algorithm correctly sorts data consisting of only 0s and 1s, then it correctly sorts any data."
I forget the exact wording, but the idea of it is that, if an algorithm meeting certain criteria works as a sorting algorithm for arrays/lists containing only two distinct values, then it works as a sorting algorithm for lists whose elements are taken from an arbitrarily large totally-ordered set.
Does anybody know anything about this? The search hits I've found are explicitly about [[sorting network]]s, but what I was taught referred to sorting algorithms more generally. Obviously not '''all''' 0-1 sorting algorithms are general sorting algorithms - [[counting sort]] with only two counters is an obvious counter-example (pardon the pun). But what are the "certain criteria"? Something that can be said about most sorting algorithms is
* the only way in which the elements are examined is to use a "less than" or "greater than" operator, which has a boolean result
* elements are moved from place to place, rather than making many copies of an element and using these as the output
But the aforementioned counting sort can be adapted to meet these criteria, so they are clearly not sufficient.
It may be the case that it is only a theorem for sorting networks, and my lecturer just intended us to use it as a heuristic test to see if a sorting algorithm seems correct. Still, can anyone provide any further insight into this, such that we might be able to add something to the article about it? — [[User:Smjg|Smjg]] ([[User talk:Smjg|talk]]) 17:42, 30 November 2013 (UTC)
| |||