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.) |
|||
| (One intermediate revision by one other user 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.
::::::::: 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)
| |||