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