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