[REBOL] How do I get the sort/compare func not to sort? Re:
From: joel::neely::fedex::com at: 20-Sep-2000 14:30
Based on the following:
>> blk1
== [8 6 4 2 0 3 7 5 1 9]
>> sort/compare blk1 func [a b] [a < b]
== [0 1 2 3 4 5 6 7 8 9]
>> sort/compare blk1 func [a b] [a > b]
== [9 8 7 6 5 4 3 2 1 0]
>> sort/compare blk1 func [a b] [(a // 2) < (b // 2)]
== [6 2 8 0 4 3 7 5 1 9]
>> sort/compare blk1 func [a b] [(a // 2) < (b // 2)]
== [2 0 6 4 8 7 3 9 1 5]
>> sort/compare blk1 func [a b] [(a // 2) < (b // 2)]
== [0 4 2 8 6 3 7 5 1 9]
>> sort/compare blk1 func [a b] [(a // 2) < (b // 2)]
== [4 8 0 6 2 7 3 9 1 5]
>> sort/compare blk1 func [a b] [true]
== [1 5 2 9 7 6 8 4 0 3]
>> sort/compare blk1 func [a b] [true]
== [0 3 7 4 6 9 5 1 2 8]
>> sort/compare blk1 func [a b] [true]
== [2 8 6 1 9 4 3 0 7 5]
I infer two things:
1) the comparison function should return true or false according
to whether its two arguments are presented in the desired order
or not, and
2) sort/compare uses an unstable sorting algorithm. That bit of
jargon that means that the result is guaranteed to satisfy the
comparison function between adjacent elements, but is there is
NO guarantee that original ordering is preserved (even among
elements that were properly ordered to begin with).
We can test the second inference by creating a comparison that uses
only part of the values, and see if the ignored portions remain in
the same relative positions:
>> blk: ["fe" "ca" "br" "ff" "cb" "bq"]
== ["fe" "ca" "br" "ff" "cb" "bq"]
>> sort/compare blk func [a b] [(first a) < (first b)]
== ["bq" "br" "ca" "cb" "ff" "fe"]
>> sort/compare blk func [a b] [(first a) < (first b)]
== ["br" "bq" "ca" "cb" "fe" "ff"]
>> sort/compare blk func [a b] [(first a) < (first b)]
== ["bq" "br" "ca" "cb" "ff" "fe"]
>> sort/compare blk func [a b] [true]
== ["cb" "ff" "br" "bq" "ca" "fe"]
>> sort/compare blk func [a b] [(first a) < (first b)]
== ["bq" "br" "cb" "ca" "fe" "ff"]
Notice that the function requires that strings be in order by their
first letter only. In each of the first three uses, that property
is clearly possessed by the result, but ordering (even original
ordering) between strings with the same first letter gets fiddled
arbitrarily.
Using a compare function which always returns true basically
lets the sort routine do whatever it wants. After that has
happened, returning to the first-letter-only sort produces yet
another ordering (in which two out of three pseudo-equal strings
change ordering from the input).
I'm out of ideas, except to say "don't sort to start with", but you
didn't hear it from me! ;-)
-jn-
[anton--globalcenter--net--au] wrote:
