Anonymous user
Talk:Order two numerical lists: Difference between revisions
→Stable Sort??
Line 53:
Where did this requirement come from? There was nothing about sorting only comparison. Neither list is touched. There is no merge or no sort. Did I miss something? --[[User:Dgamey|Dgamey]] 03:24, 30 November 2011 (UTC)
: Rereading this the description as it stands could mean either sort or determine with list is less. If it's a sort, should not the task name be Sort two numerical lists? --[[User:Dgamey|Dgamey]] 03:46, 30 November 2011 (UTC)
:: a comparison function is generally used as an operator for a sort function. the result of the comparison function determines how the sort comes out.--[[User:EMBee|eMBee]] 05:50, 30 November 2011 (UTC)
::
::: yes. --[[User:EMBee|eMBee]] 05:50, 30 November 2011 (UTC)
:: If so, it's bunk: sort stability depends more on the sort method than the comparator.--[[User:Ledrug|Ledrug]] 04:33, 30 November 2011 (UTC)
::: true, but if both elements are the same then it makes a difference if true or false is returned. how do you account for that difference? i think there are two aspects to stable, one is: when you rerun the sort it will always produce the same result. this stability depends on the algorithm. the other is, that if two elements are equal, their order will not be changed. that stability depends on the comparator. and according to [[wp:Sorting_algorithm#Stability|wikipedia]]: ''Stable sorting algorithms maintain the relative order of records with equal keys.'' the equality of keys is determined by the comparator.--[[User:EMBee|eMBee]] 05:50, 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)
:: it's not necessarily desirable to sort shorter lists before longer ones (one may prefer padding by zero, i.e. (1, 2, -1) < (1, 2) < (1, 2, 1), rather than padding by -inf, i.e. (1, 2) < (1, 2, -1) < (1, 2, 1)). --[[User:Ledrug|Ledrug]] 04:33, 30 November 2011 (UTC)
::: yes, but we should choose one or the other. as it happens the current choice matches lexicographical ordering. so i think it's an appropriate choice--[[User:EMBee|eMBee]] 05:50, 30 November 2011 (UTC)
==Lexicographic order==
| |||