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