OpenEuphoria

miraculous sort revisited

• Posted by Robert Craig <robert_craig at COMPUSERVE.COM> Feb 25, 1997
• 1361 views

Jacques Deschenes writes:

> I say that the array indexing is what do for the comparison.

I still think there aren't any actual compares being done, but
that is not what interests me the most about this sort.
The really interesting thing is that bucket sort is FAST!
I modified it a bit to take out the '&' and the repeat().
With those minor modifications it now sorts 10,000 numbers
more than *10 times faster* than the standard Euphoria sort()
in sort.e. It's the sorting method that they never teach
you in school, yet it's the fastest in many cases.
(Of course it's hard to apply this method to floating-point
numbers, strings, or integers that span a huge range.)


---------- new bucket sort ------------------------------

without type_check

function bucket_sort(sequence s, integer min_value, integer max_value)
-- Sort s into ascending order. No elements are (directly!) compared.
-- The values of s must be integers from min_value to max_value
    sequence count, sorted
    integer value, k

    count = repeat(0, max_value-min_value+1)
    s = s - (min_value - 1)
    for i = 1 to length(s) do
        value = s[i]
        count[value] = count[value]+1
    end for
    sorted = repeat(0, length(s))
    k = 1
    for i = 1 to length(count) do
        -- inner loop modified to go faster:
        for j = 0 to count[i]-1 do
            sorted[k] = i
            k = k + 1
        end for
    end for
    return sorted + (min_value - 1)
end function

include sort.e

sequence unsorted, sorted1, sorted2
atom t

-- 10,000 random numbers in the range 1 to 1000
unsorted = rand(repeat(1000, 10000))

-- time the bucket sort:
puts(1, "bucket sort: ")
t = time()
for i = 1 to 100 do
    sorted1 = bucket_sort(unsorted, 1, 1000)
end for
? time() - t

-- time the standard Euphoria sort:
puts(1, "standard sort: ")
t = time()
for i = 1 to 100 do
    sorted2 = sort(unsorted)
end for
? time() - t

-- compare results:
if compare(sorted1, sorted2) != 0 then
    puts(1, "bad sort!\n")
end if

------------------------------------------------

Regards,
   Rob Craig
   Rapid Deployment Software