Anonymous user
Talk:Order two numerical lists: Difference between revisions
→Is the task statement consistent?
(<= not required for sorting) |
|||
Line 124:
:: 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.''
| |||