OpenEuphoria

Re: random_sort (was Re: no response?)

• Posted by Jeffrey Fielding <JJProg at CYBERBURY.NET> Sep 19, 1998
• 679 views

Here is my solution to the random sort problem.

Jeff Fielding
JJProg at cyberbury.net






-- A really slow random sort function
-- I don't understand the rules perfectly, so tell me if it's ilegal
function random_sort(sequence s)
    sequence sorted, checked
    object t
    integer a, b
    sorted = s
    checked = repeat(0,length(s))
    for i = 1 to length(s) do
        checked[i] = i
    end for
    while length(checked) do
        a = rand(length(checked))
        b = rand(length(checked))
        a = checked[a]
        b = checked[b]
        if compare(sorted[a],sorted[b]) = 1 then
            t = sorted[a]
            sorted[a] = sorted[b]
            sorted[b] = t
        end if
        if get_key() != -1 then
            exit
        end if
        a = 1
        checked = {}
        for i = 1 to length(sorted)-1 do
            if compare(sorted[i],sorted[i+1]) = 1 then
                a = 0
                checked = checked & {i,i+1}
            end if
        end for
        if a = 1 then
            exit
        end if
        ? sorted
    end while
    return sorted
end function
function old_random_sort(sequence s)
    sequence sorted, checked
    object t
    integer a, b
    sorted = s
    checked = repeat(0,length(s))
    while find(0,checked) do
        a = rand(length(s))
        b = rand(length(s))
        if checked[a] = 0 or checked[b] = 0 then
            if compare(sorted[a],sorted[b]) = 1 then
                t = sorted[a]
                sorted[a] = sorted[b]
                sorted[b] = t
            end if
        end if
        if get_key() != -1 then
            exit
        end if
        a = 1
        checked = repeat(1,length(sorted))
        for i = 1 to length(sorted)-1 do
            if compare(sorted[i],sorted[i+1]) = 1 then
                a = 0
                checked[i] = 0
            end if
        end for
        if a = 1 then
            exit
        end if
        ? sorted
    end while
    return sorted
end function
sequence s, tm
atom t
s = {}
for i = 1 to 7 do
    s = s & rand(10)
end for
t = time()
? random_sort(s)
t = time() - t
tm = {t}
t = time()
? old_random_sort(s)
t = time() - t
tm = tm & t
printf(1,"%f    %f",tm)