Mailing List Archive: 49091 messages

# How do I get the sort/compare func not to sort?

### [1/4] from: anton:globalcenter:au at: 21-Sep-2000 6:01

Hello, Given, s: "abvde" sort/compare s func [a b][return 0] What can I exchange for the 0 return value such that the input is left unchanged? (and no, the answer is not "don't sort to start with" :-) I've tried -1, 0, 1. They all change the string! Anton.

### [2/4] 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:

### [3/4] from: holger:rebol at: 20-Sep-2000 13:15

On Wed, Sep 20, 2000 at 02:30:50PM -0500, [joel--neely--fedex--com] wrote:
> 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.
Correct on both points. The current sort function does have its limitations... One of the next experimental builds will have a significantly improved sort function, which uses a stable sort algorithm and provides several additional options and refinements (hierarchical/lexicographical sorting etc.) -- Holger Kruse [holger--rebol--com]

### [4/4] from: lmecir:geocities at: 20-Sep-2000 22:18

Hi, there is a help, but you must use a stable sorting algorithm, eg. my Merge-sort could do what you want (can send you my %msort.r privately). Regards Ladislav