## sort without compare: the count sort

j_milton
Posts: 458
Joined: Feb 11, 2010 17:35

### sort without compare: the count sort

Here:
http://freebasic.net/forum/viewtopic.php?p=132745
Relsoft shows a sort he calls "table sort" and asks for benchmarks vs. Quicksort, which I have not done but maybe something useful to add. I don't think "table sort" is a "standard" algorithm name, or at least not widely used, but looking at the code it's a variant on the "count sort" which is a type of "bucket sort" / "bin sort" / "histogram sort". These terms may be of use if you want to do more research on these methods.

In general, for short unsorted lists (100's of items) a comparison sort like "Quick" or "Comb" may well be close due to fixed overhead in generic count sorts, but with larger lists (> 100,000) non-comparison sorts like the count sort can really smoke the competition since they run in time linear to the size of the unsorted list as opposed to comparison sorts which run in some exponential time depending on the algorithm.

The downside is the need for extra storage proportionate to the range of data in the input, and messy stuff required if the input is not a simple integer type, but for certain applications they are a tool worth having for sure.

Below is a console mode comparison of a fairly "generic" count sort vs comb sort.

benchmarks on a p4 machine are as follows; with 1000 items in unsorted list:
Comb sort: 0.0004 seconds
Count sort: 0.0001 seconds
With 1,000,000 items in unsorted list:
Comb sort: 0.531 seconds
Count sort: 0.023 seconds

Code: Select all

`' demo of the comb sort  and count sort algorithmsSub combsort(a() As Integer)    Dim As Integer i, j, gap,swaps, first, last    first = LBound(a)   last = UBound (a)      gap = last - first + 1   Do      gap = Int(gap / 1.3)      If gap = 9 Or gap = 10 Then         gap = 11        Else         If gap < 1 Then            gap = 1         EndIf         EndIf      i = first      swaps = 0       j = i + gap      Do           If a(i) > a(j) Then              Swap a(i), a(j)              swaps = 1            End if           i += 1           j = i + gap      Loop Until j > last   Loop Until (gap = 1) and (swaps = 0)End Sub 'combsortSub countsort(a() As Integer)   Dim As Integer count, first, last, min, max, x      'first find the largest and smallest values in a()   first = LBound(a)   last = UBound(a)   min = a(first)   max = a(first)   first += 1   For count = first To last       If a(count) > max Then         max = a(count)      Else         If a(count) < min Then            min = a(count)         EndIf      EndIf   Next   first -= 1      'create the secondary array   ReDim As Integer bins(min to max)      'fill the secondary array    For count = first To last      bins(a(count)) += 1   Next      'overwrite a() with the sorted data   x = first   For count = min To max      Do While bins(count) > 0         a(x) = count         x += 1         bins(count) -= 1      Loop   Next   End Sub 'countsortredim  As Integer a(1 To 1000000),  b(1 To 1000000)Dim As Double st, etDim As Integer count'fill the array with random numbersFor count = LBound(a) To UBound(a)   a(count) = rnd * 1000   b(count) = a(count)Next'sort itst = timercombsort(a())et = TimerPrint "Comb sort:"For count = LBound(a) To UBound(a)   'uncomment the following to see the sorted data   'Print a(count),Next'print the elapsed time needed to do the sortPrint "Time to sort " & UBound(a) &": " & et-st & " seconds"'sort itst = timercountsort(b())et = TimerPrint "Count sort:"For count = LBound(b) To UBound(b)   'uncomment the following to see the sorted data   'Print b(count),Next'print the elapsed time needed to do the sortPrint "Time to sort " & UBound(b) &": " & et-st & " seconds"Print "Done, press any key to end"sleep`
relsoft
Posts: 1767
Joined: May 27, 2005 10:34
Location: Philippines
Contact:
Thanks for the clarification. The tutorial at gamedev.net called it table sort. It's kinda like how the 1d z-buffer in 3d engines work.

600 mhz celeron.

Comb sort:
Time to sort 1000000: 4.295979516949956 seconds
Count sort:
Time to sort 1000000: 0.1934533578987612 seconds
Done, press any key to end
j_milton
Posts: 458
Joined: Feb 11, 2010 17:35

### non-comparison sorts

You're welcome. When used in a real application like a graphics engine the code would wind up being a lot more like your example, the one I coded in the benchmark demo was just sort of stripped down to try and illustrate the core concept of the algorithm.

One of the neat things about these kind of sorts is that you don't have to have all the raw data prior to starting to sort, which makes them ideal for certain real time or continuous flow system control applications.

For example a variation called, not surprisingly, the "Postmans sort" is used in automatic mail sorting machines at the post office where each data item is an address on an envelope that needs to be routed for distribution.