Talk:Order two numerical lists

From Rosetta Code

The task description should clarify what should happen for two equal lists.

Right now the description seems inconsistent. It says "return true if the first list should be ordered before the second", but should a list be ordered before itself? It seems that it should not.

if both lists are the same then, they still have to go in some order. so there is no inconsistency. you can not not order them. which order they go then depends on the comparison though, and that affects whether the sort is stable or not. as it is defined the task does not expect the solution to produce a stable sort. such a requirement could be added, but then the existing solutions need to be reviewed. since both stable and unstable sort have legitimate uses i don't want to make unstable sort wrong. it could be added as extra credit though--eMBee 02:30, 30 November 2011 (UTC)

But reading the algorithm description: "... and so on, until one of the list has no more elements. If the first list runs out of elements the result is true." It seems that it should return true for two equal lists, since both lists would run out of elements at the same time.

if the first list is tested first, and the second list is not tested, the effect is that if both are equal, the result will be true.--eMBee 02:30, 30 November 2011 (UTC)
"ordered before" is the familar concept of "less than." For programming anyway, less than always means strictly less than and never less than or maybe equal to. A fix would be to change "If the first list runs out of elements the result is true. false otherwise" to "If the first list runs out of elements while there are still elements left in the second the result is true. false otherwise." Then you have strictly less than semantics...which could be used to write a stable sort algorithm. —Sonia 04:09, 30 November 2011 (UTC)
I would be in favor of clarifying the required behavior when lists are equal, removing all talk of sorting from the task description, and requiring output from three test cases: one where the first list should be ordered before, one where the lists are equal, and one where the second list should be ordered before. —Sonia 04:29, 30 November 2011 (UTC)

Whatever is decided, some of the solutions will be incorrect and will need to be changed. --Spoon! 23:55, 29 November 2011 (UTC)

This probably should be marked draft until decided. So I changed it. --Dgamey 03:21, 30 November 2011 (UTC)
Adding in extra conditions like stable sort when the task is NOT marked draft is rather bad form --Dgamey 03:21, 30 November 2011 (UTC)

Test Cases

I found the description a bit confusing at first. I used the following test cases where demo_list_llt was a wrapper to support my interpretation. This is based on ordering being to choose which of two lists comes first (not sorting). --Dgamey 03:24, 30 November 2011 (UTC) 

   write()
   demo_list_llt([-1],[0])                         # << ok
   demo_list_llt([0],[0])                          # == fail 
   demo_list_llt([0],[-1])                         # >> fail
   write()
   demo_list_llt([0],[0,-1])                       # << ok   
   demo_list_llt([0],[0,0])                        # << ok     
   demo_list_llt([0],[0,1])                        # << ok 
   demo_list_llt([0,-1],[0])                       # >> fail 
   demo_list_llt([0,0],[0])                        # >> fail
   demo_list_llt([0,0],[1])                        # << ok

With the following output:

[ 1 2 1 3 2 ] << [ 1 2 0 4 4 0 0 0 ] - FAILS

[ -1 ] << [ 0 ]
[ 0 ] << [ 0 ] - FAILS
[ 0 ] << [ -1 ] - FAILS

[ 0 ] << [ 0 -1 ]
[ 0 ] << [ 0 0 ]
[ 0 ] << [ 0 1 ]
[ 0 -1 ] << [ 0 ] - FAILS
[ 0 0 ] << [ 0 ] - FAILS
[ 0 0 ] << [ 1 ]

The wrapper and support routine in Icon was 

procedure demo_list_llt(L1,L2)
   write(list2string(L1)," << ",list2string(L2),if list_llt(L1,L2) then "" else " - FAILS")
end   

procedure list2string(L1)
every (s := "[") ||:= " " || (!L1|"]")
return s
end

Stable Sort??

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? --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? --Dgamey 03:46, 30 November 2011 (UTC)
Since the task doesn't seem to have anything to do with sorting, I removed the mention of stable sort for now. I guess the intention was that if the cmp function is used for a comparison based sorting, it should produce a stable sort result. If so, it's bunk: sort stability depends more on the sort method than the comparator.
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; 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)). --Ledrug 04:33, 30 November 2011 (UTC)

Lexicographic order

Isn't lexicographic order the one where the integer 100 comes before the integer 11? That is, I thought that it was a character set based comparison rather than a numeric comparison. Stormneedle 04:26, 30 November 2011 (UTC)

No. "Lexicographic" only refers to the list as whole, not when comparing its individual elements. The elements are compared by whatever is natural, which probably means numerical comparison function (100 > 11, 11 > 2). --Ledrug 04:33, 30 November 2011 (UTC)
Well that wasn't clear. So doesn't that imply no padding? --Dgamey 04:47, 30 November 2011 (UTC)
Retrieved from "https://rosettacode.org/wiki/Talk:Order_two_numerical_lists?oldid=208092"