Anonymous user
Talk:Order two numerical lists: Difference between revisions
m
added a section name to the first talk topic, this will also place the TOC correctly.
m (added a section name to the first talk topic, this will also place the TOC correctly.) |
|||
| (4 intermediate revisions by 3 users not shown) | |||
Line 1:
== clarify what should happen for equal lists ==
The task description should clarify what should happen for two equal lists.
Line 64 ⟶ 65:
:::::: You can use a comparison routine in a bubble sort and claim it's "stable", then use it in a quicksort and find that it's not--you are still missing the point: sort stability is not the property of the comparator ''at all''. Seeing that the matter is probably settled anyway, I'm just point that out as a final clarification. --[[User:Ledrug|Ledrug]] 08:42, 30 November 2011 (UTC)
:::::::i am not disagreeing with that, but the implied claim that a stable sort routine is guraranteed to be stable regardless of the comparator used. to use your words: ''you can use a comparison routine in a bubble sort and claim it's "stable", and then ''use a different comparison routine'' and find that it's not.'' the stability depends on a combination of both. or in other words, the stability depends on the sort routine knowing when two elements are equal, which it can not know if it only has one boolean comparison routine.--[[User:EMBee|eMBee]] 09:14, 30 November 2011 (UTC)
:::::::: Well, a sane comparison routine can ''always'' know if stuff are equal: if you define operator "less than", and both <math>a < b</math> and <math>b < a</math> are false, they are equal. If you define operator "less or equal", and both <math>a \leq b</math> and <math>b \leq a</math> are true, they are equal.--[[User:Ledrug|Ledrug]] 19:00, 30 November 2011 (UTC)
::::::::: ah, yes, indeed. i didn't consider testing both <code>a,b</code> and <code>b,a</code>.--[[User:EMBee|eMBee]] 15:06, 2 December 2011 (UTC)
:::::::: But note the requirement of being sane: if you define the "less than" in such a way that there might be a case where both <math>a < b</math> and <math>b < a</math> are true, then the whole thing is quite screwed (such as before you changed the task definition when it said "if a runs out, a < b" while ignored the case where b might be out at the same time.) --[[User:Ledrug|Ledrug]] 19:00, 30 November 2011 (UTC)
:: Another thing, it might be better to omit some detailed requirement about the cmp result. To be practical, the cmp routine should be able to decide on the ording. For example, it's likely more useful for a comparison function to be tri-state instead of true/false;--[[User:Ledrug|Ledrug]] 04:33, 30 November 2011 (UTC)
::: tri-state does not work as input to a sort function unless the sort function is written for that. most sort function i i'd expect to want a boolean comparator.--[[User:EMBee|eMBee]] 05:50, 30 November 2011 (UTC)
Line 129 ⟶ 133:
(Although it might invalidate earlier solutions). --[[User:Paddy3118|Paddy3118]] 17:45, 30 November 2011 (UTC)
::well, the current definition asks to return false if both are equal, but it matches the original intent (the treatment of equal lists was only clarified today anyways and is only relevant for sorting stability, which as we learned above also depends on the sorting algorithm which is beyond the scope of the task). --[[User:EMBee|eMBee]] 18:14, 30 November 2011 (UTC)
:::Hi eMBee, If you leave it as it is, you would have the first paragraph say one thing and the second another. If you want the ordering to come from that referenced wikipedia article on lexicographic ordering then it seems your first paragraph does not agree with it (the second seems to though). --[[User:Paddy3118|Paddy3118]] 17:35, 1 December 2011 (UTC)
:::: sorry, upon rereading my text i realize that it is ambiguous. what i meant to say is: ''the current definition asks to return false if both are equal, but '''your suggestion''' matches the original intent'', which is to say, that your suggestion is good. (and the rest is about the ''return false if both are equal'' not being important)--[[User:EMBee|eMBee]] 15:01, 2 December 2011 (UTC)
| |||