Always-unstable is trivial: use a stable sort, and the first time you encounter two elements that compare equal, swap them. The problem with that is it isn't necessarily detectably unstable. The two elements you swap might be equal in all ways. To be detectably unstable, you need the sort function to know when two elements that compare equal are not otherwise equal, so you have to pass it a second comparison function, and if you can do that why are you bothering with an unstable sort in the first place? I think I'm confused about the point of "always unstable".
An alternate interpretation of "always unstable" is for sort to throw an error anytime it encounters two elements that compare equal. Which is pretty annoyingly useless. You might as well just use a stable sort all the time. On Thu, Jun 13, 2013 at 3:10 PM, Sean Silva <[email protected]> wrote: > On Thu, Jun 13, 2013 at 12:16 PM, Kevin Gadd <[email protected]> wrote: >> >> I don't understand why you would intentionally sidetrack a discussion >> about a simple problem with academic details. > > > He brings up a very real point, which is that you can't realistically have > an "always unstable" sort. If I understand you correctly, what you want by > an "always unstable" sort is that you want developers to "get bitten" in > testing due to instability, even for small test cases, so that the issue is > caught earlier. The problem with that desire is that there are no sorting > algorithms AFAIK that guarantee that they will *always* rearrange > equal-sorting elements (i.e., "always unstable"): even a pure recursive > quicksort (no insertion-sort base case) will sometimes not rearrange > equal-sorting elements (i.e., seem stable). > > If I understand your desire correctly, then what you're asking for by > "always unstable" is to require that if an implementation's sorting > algorithm *might* rearrange equal-sorting elements, then it must *always* go > out of its way to ensure that if equal-sorting elements are present, then it > does not preserve their order; I haven't looked in detail at what this would > mean from an implementation standpoint, but I'm pretty sure that it is > unrealistic. > > -- Sean Silva > > _______________________________________________ > es-discuss mailing list > [email protected] > https://mail.mozilla.org/listinfo/es-discuss > _______________________________________________ es-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es-discuss
