OpenEuphoria

Re: integer_median, Lucius, me and that.

• Posted by Tor Gausen <tor.gausen at C2I.NET> Jun 12, 2000
• 399 views

[Oops! I think I first sent this message to Michael Nelson instead of
the list:]

I finally found a faster median function (all on my own , although
it will only work with integers as it is heavily inspired by good old
bucket sort:

function integer_median(sequence s)
    sequence c
    integer v, k, o, l, t, b

    l = length(s)
    b = s[1]
    t = b
    for n = 1 to l do
        v = s[n]
        if v > t then
            t = v
        elsif v < b then
            b = v
        end if
    end for

    c = repeat(0, t - b + 1)
    o = b - 1
    for n = 1 to l do
        v = s[n] - o
        c[v] += 1
    end for

    k = 1
    v = 0
    while v < l / 2 do
        v += c[k]
        k += 1
    end while

    return k - 1 + o

end function

Sorry Mike, it does not average the middle pairs, but this can be
defended to a certain extent, since it guaranties you'll end up with
a 'real' value which was actually in the distribution.

Lucius is OK, I'm OK and that's OK 
Tor