Hi,
don't know, what is the problem, but here is a merge-sort working
for me looong time:
REBOL[
Title: "Merge Sort"
Author: "Ladislav Mecir"
Email: [EMAIL PROTECTED]
Date: 9/2/1998
Purpose: {
Merge sort a series
}
]
msort: function [a compare] [msort_do merge] [
; Define a recursive MSORT_DO function
msort_do: function [a l] [lb] [
either (lb: make integer! (:l / 2)) = 0 [copy/part :a :l]
[
merge (msort_do :a :lb) (msort_do skip :a :lb (:l -
:lb))
]
]
; Function MERGE is the key part of the algorithm
merge: function [a b] [res] [
res: make block! (length? :a) + (length? :b)
until [
either (compare first :a first :b) [
res: insert :res first :a
tail? (a: next :a)
] [
res: insert :res first :b
tail? (b: next :b)
]
]
either tail? :a [insert :res :b] [insert :res :a]
head :res
]
msort_do :a length? :a
]
{
time: func [] [fourth now]
; return random series containing integers
serf: function [l] [b i] [
b: make block! l
for i 1 l 1 [b: insert b random l]
return head b
]
compare: func [a b] [
return a <= b
]
foreach size [10 100 500 1000] [
b: serf size
start: time
b: msort :compare b
finish: time
print [size (finish - start)]
]
}
Hi again
Boy, all those problems...
Try running the attached script. It gives the following error:
** Script Error: middle has no value.
** Where: copy skip list middle
OK... well, the line with "copy skip list middle" is just _below_
this line:
list1: sort-list (copy/part list middle) :cfunc
which doesn't produce an error, and since I don't touch 'middle
between those
two lines, 'middle _has_ to have a value!
I suspect that 'use is broken. For recursion I need 'use,
otherwise the
recursive calls will mess with the variables. But it seems like
'use causes
recursive calls to unset the used variables.
Any ideas what else could be wrong, before I send this to
[EMAIL PROTECTED]?
I know that it might just be me having made a stupid bug in the
attached
code.
BTW, the attached function is a merge-sort, which I had to write
since
bubble-sort is too slow, and since I still haven't got
sort/compare working
(will be sending this bug report to [EMAIL PROTECTED] soon too,
unless
somebody can see if there's an error in my code). I know that
merge-sort can
be implemented in a less memory-hungry way, but I'd like to get
this thing
working first.
Kind regards,
--
Ole Friis <[EMAIL PROTECTED]>
Amiga is a trademark of Amiga Inc.
------------------------------------------------------------------
--------------
> REBOL []
>
> sort-list: func [list cfunc] [
> use [list1 list2 middle] [
> if (length? list) > 1 [
> ; Recursively sort the two halves of list
> middle: to-integer ((length? list) / 2)
> list1: sort-list (copy/part list middle) :cfunc
> list2: sort-list (copy skip list middle) :cfunc
>
> ; Merge list1 and list2 into list
> clear list
> while [(not tail? list1) and (not tail? list2)] [
> either (cfunc (first list1) (first list2)) [
> append list first list1
> list1: next list1
> ] [
> append list first list2
> list2: next list2
> ]
> list: next list
> ]
> append list list1
> append list list2
> ]
> ]
> list
> ]
>
> test-list: [6 5 3 8 9]
> sort-list test-list :greater?
>
