7 ms·
That's not a proper sort. A sort is not just a function that takes in a list and returns a list that is sorted. The result must also include all of the elements
by charcircuit 5y ago
That's not a proper sort. A sort is not just a function that takes in a list and returns a list that is sorted. The result must also include all of the elements that you had when starting. That property isn't checked by the code you linked.
- layer8 5y agoSomeone should calculate how many copies of the array you need (as a function of input data size) to make that sorting strategy work with reasonable assurance that the original data is maintained.
- deleted 5y ago[deleted]
- hvdijk 5y agoDo you know of any sort routine that guarantees the result includes all of the input elements even in the event of random bit flips? If not, do you consider the sorting routines in your everyday libraries improper as well or is that a special restriction reserved for this particular implementation?
- tshaddox 5y agoNo, when we normally talk about code we have some vague notion of a formal system that works according to its specification, and thus that !isSorted loop example is pretty clearly invalid. And even if you do allow for random bit flips, surely that’s more likely to happen to the boolean returned by isSorted than for enough bits to flip to make the array sorted.
- hvdijk 5y agoThe objection that the GP raised, the lack of a check that the result includes all of the elements of the input, is not needed under your notion of a system that works according to its specification, as according to that specification it is a loop invariant. It is also not useful, as it is an infinite loop. Your view of why cosmic ray sort is not a proper sort therefore contradicts GP's explanation, even if you share the GP's conclusion. My question was aimed at further exploring the GP's view; I think an opposing view does not help here.
- Gravyness 5y agoYou're arguing that the code that uses internal failure as functionality is invalid? Damn, I wish I had your kind of expertise.