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.) |
|||
| (8 intermediate revisions by 4 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 123 ⟶ 127:
:: Note that by convention, when we say "condition such and such for all i in set A" and A turns out to be empty, this condition is considered sastified.
:: Also note that, the task seems to have sorting in mind; however, if elements can be equal to each other, you ''must'' have a <math>\leq</math> comparison instead of <math><</math>, so equality also needs to be defined. The reason: a list <math>a</math> is considered sorted if for any pairs of indices <math>i, j</math> where <math>1 \leq i \leq j \leq M</math>, the condition is met: <math>a_i \leq a_j</math>. The last term can't be stated as <math>a_i < a_j</math> if elements may compare equal, or list (1, 2, 2) will not have a sorted permutation. --[[User:Ledrug|Ledrug]] 09:26, 30 November 2011 (UTC)
:::No, just because <= is meaningful doesn't mean that a <= operator is required for sorting. (a < b) == !(b <= a) Any of <, <=, >, or >= could be used to write a sorting algorithm, stable or otherwise. —[[User:Sonia|Sonia]] 18:28, 30 November 2011 (UTC)
:::: I was not talking about the sorting process, but the well-definedness of a sorted list, for which you'll need a transitive equality relation if any two elements <math>a</math> and <math>b</math> can fail both <math>a < b</math> and <math>b < a</math> conditions, that is, <math>a = b</math>. Basically, if <math>a = b</math>, and <math>a < c</math>, then the comparison must also yield <math>b < c</math>, else you won't have a definable sorted state, let alone a function to reach it. --[[User:Ledrug|Ledrug]] 18:50, 30 November 2011 (UTC)
Seems to me then that my pseudo-code matches Ledrugs maths (thanks). The first quote from the task description is therefore wrong. Maybe it could be replaced with:
:''The function should accept two lists as arguments and return <code>true</code> if the first list lexicographically precedes or is equal to the second, or <code>false</code> otherwise.''
(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)
| |||