sort without compare: the count sort

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
j_milton
Posts: 458
Joined: Feb 11, 2010 17:35

sort without compare: the count sort

Postby j_milton » Mar 29, 2010 17:06

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 algorithms

Sub 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 'combsort

Sub 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 'countsort

redim  As Integer a(1 To 1000000),  b(1 To 1000000)
Dim As Double st, et
Dim As Integer count

'fill the array with random numbers
For count = LBound(a) To UBound(a)
   a(count) = rnd * 1000
   b(count) = a(count)
Next

'sort it
st = timer
combsort(a())
et = Timer

Print "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 sort
Print "Time to sort " & UBound(a) &": " & et-st & " seconds"

'sort it
st = timer
countsort(b())
et = Timer

Print "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 sort
Print "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:

Postby relsoft » Mar 30, 2010 3:09

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

Postby j_milton » Mar 30, 2010 4:48

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.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 1 guest