OpenEuphoria

miraculous sort revisited

• Posted by Jacques Deschenes <desja at QUEBECTEL.COM> Feb 24, 1997
• 936 views

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