### 1. miraculous sort revisited

- Posted by Jacques Deschenes <desja at QUEBECTEL.COM> Feb 24, 1997
- 545 views
- 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

- Posted by Robert Craig <robert_craig at COMPUSERVE.COM> Feb 25, 1997
- 538 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