1. Enhanced bucket sort
Hello all:
I found that the Enhanced bucket sort by Art Adamson crashes when faced
with
sequences. A set of sequences such as {12, 34, {23, 21}} or anything of the
like will simply crash his bucket sort.
My Flexible bucket sort does not fail under such pressure.
Mine also doesn't require any type of limited range. Just like all other
bucket sorts it draws its strength from multiple occurances of data.
Example: If the data to be sorted was something like
{{12, {34}}, {12, {54}}, {12, {34}}, {12, {54}}, {13, {6}}}
then a bucket sort will draw speed from the fact that
the value {12, {34}} and the value {12, {54}} are repeated
-------------------------
-- bucket.e
-------------------------
-- Flexible bucket sort
-- Lucius L. Hilley III
-- 05-16-1999
-------------------------
include sort.e
global function bucket_sort(sequence s)
integer l, f
object temp
sequence bucket, value, s_value, s_bucket, sorted
value = {}
bucket = {}
sorted = s
l = length(s)
for A = 1 to l do
f = find(s[A], value)
if f then
bucket[f] = bucket[f] + 1
else
value = append(value, s[A])
bucket = bucket & 1
end if
end for
s_value = sort(value)
s_bucket = bucket
for A = 1 to length(s_value) do
f = find(s_value[A], value)
s_bucket[A] = bucket[f]
end for
f = 1
for A = 1 to length(s_bucket) do
l = s_bucket[A]
temp = s_value[A]
for B = f to f + l - 1 do
sorted[B] = temp
end for
f = f + l
end for
return sorted
end function
procedure test()
atom t
sequence s, s1, s2, temp
temp = {256, {256, 256, {256}}}
s = rand(repeat(temp, 4096))
t = time()
s2 = bucket_sort(s)
? time() - t
t = time()
s1 = sort(s)
? time() - t
? compare(s1, s2)
end procedure
test()
-------------------------------
Lucius L. Hilley III
