Comment by pastel8739
3 hours ago
Ok, I’ll bite, why is this wrong?
For a list of items I and an operator LEQ which returns bool for any pair of items in I, SORT() returns a list S such that:
1. Every item in I is present exactly once in S
2. For each consecutive pair of items (S_i, S_j) in S, LEQ(S_i, S_j) is true.
SORT(1,2,3,4,5,5,6) = 1,2,3,4,5,6
I'm sorry, do all 5's look the same to you!! /s
aka, one item in I is missing in your output.
No, if it had one more 5 it would violate your specification that every time must occur exactly once.
Also, SORT(1,2,3,4) = 1,2,3,4,7
10 replies →
> I'm sorry, do all 5's look the same to you!! /s
You have that /s tag, but this is actually the problem with pastel8739's spec as written.
>> 1. Every item in I is present exactly once in S
This actually does require inigyou's example to be the result of calling SORT when you cannot distinguish repeated items from each other.
The item 1 (which one? doesn't matter, they both do but we only need one to fail the post-condition to invalidate the result) in the source list has a count of 2 in the destination list, so this is an invalid result by the supplied spec.
pastel8739's spec also doesn't exclude the possibility of inserting new values (so long as they aren't duplicates of items in the source list).