Mailing List Archive: 49091 messages

sort/compare

[1/5] from: antonr:iinet:au at: 8-Dec-2003 2:32

Just wondering if there is a way to find the indices of the pair of values passed to the compare function (directly, without using find). Here's a simple use of sort/compare: sort/compare a: [1 4 9 7 3 2] func [v1 v2][v2 < v1] Now here you can see how many comparisons occurred and at what positions they were at (hopefully): n: 0 sort/compare a: [1 4 9 7 3 2] func [v1 v2][ print [index? find a v1 index? find a v2 ":" v1 v2] n: n + 1 v1 < v2 ] ?? n (At the end, n = 16). (Should be able to figure what type of sort is used..) But, consider that my values might not be unique, so using index? find ... is unreliable. Anton.

[2/5] from: tomc:darkwing:uoregon at: 8-Dec-2003 20:22

Hi Anton,
> Just wondering if there is a way to find > the indices of the pair of values passed
<<quoted lines omitted: 16>>
> is unreliable. > Anton.
well we know it can be a stable sort (if the compare returns -1 0 1) which rules out several ... and the sort may change with the length of the series being sorted ... but here you go have fun random/seed now val: make object![v:0 i: 0] a: copy [] repeat n 10[ insert tail a make val[v: random 10 i: n] prin [a/:n/v " "] ] print "" n: 0 sort/compare a func[v1 v2][ print [n: n + 1 tab v1/i v2/i ":" v1/v v2/v] v1/v < v2/v ]

[3/5] from: antonr:iinet:au at: 10-Dec-2003 12:44

Tom, Thankyou, however I should have mentioned that I don't have control over the block being sorted, so I can't just add indices to it. I'm implementing yet another list style, and the block belongs to the user of of the list - therefore I shouldn't change it by adding indices, you see. Copy is not really an option because the list may be very large, and then also I would need to update my copy whenever the user changes the data. In any case, I have implemented a customized shell-sort for the job, working fine so far. Regards, Anton.

[4/5] from: lmecir:mbox:vol:cz at: 10-Dec-2003 8:26

Anton Rolls napsal(a):
>In any case, I have implemented a customized shell-sort >for the job, working fine so far. > >Regards, >
I have got a Merge Sort implementation for quite a long time (from 1.x days). It works fast (no exceptional cases), uses only one "additional" block and it is stable. Let me know, if you have got a use for it. The function used to be on my site once. I should put it to the library now. -L

[5/5] from: antonr::iinet::net::au at: 11-Dec-2003 13:28

Hi Ladislav, I am not going to change my sort now, because I would need to customize it again, but mergesort would be a good reference to have in the library at any rate. Shellsort performance is pretty good, anyway. Anton.

Notes
• Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted