1. miraculous sort revisited
- Posted by Jacques Deschenes <desja at QUEBECTEL.COM>
Feb 24, 1997
-
Last edited Feb 25, 1997
Sunday, Fev. 23th, Robert Craig proposed a sort without any comparison:
function bucket_sort(sequence s, integer min_value, integer max_value)
>-- Sort s into ascending order. No elements are compared.
>-- The values of s must be integers from min_value to max_value
> sequence count, sorted
> integer value
>
> 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 = {}
> for i = 1 to length(count) do
> sorted = sorted & repeat(i, count[i])
> end for
> return sorted + (min_value - 1)
>end function
>
>? bucket_sort({25,7,2,5,200,14,7,10}, 1, 256)
Hi Robert,
The bucket sort, leaved me stupified, so I decided to
give it a deeper thougth. Of course at euphoria level there is no comparison.
This is because the comparison is done at machine code level.
The comparison is hidden in the array indexing mechanism.
to access a location in an array, to store or retreive the data,
the index is added to te base memory location of the array.
This indexing mechanism hidden at lower level is what take place of
comparison.
You could say that adding is not comparing and I would say yes it is.
If we look at the mechanism by which the cpu compare to value we see it is
the same circuit that is used.
In effect an assembler instruction like: cmp ax, value
in fact substract value to the containt of ax without
storing the result in ax.
But we know that there is no logical circuit for substraction.
A substraction is obtained by first taking the two's complement of
the operand to be substracted then adding it to the first
operand.
So a CMP instruction imply a NOT operator to obtain one's complement
then adding 1 to that inverted number to get the two's complement and
finally making the ADDITION.
While indexing is a straight ADDITION (+ maybe MULTIPLICATION for scaling the
index.)
I say that the array indexing is what do for the comparison.
Jacques Deschenes
Baie-Comeau, Quebec
Canada
desja at quebectel.com
2. miraculous sort revisited
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
