Table sort. Fastest sort algo I've ever come to know...

[dodicat]

C runtime qsort versus standard Quicksort.

Code: Select all

#include "crt/stdlib.bi"

Function callback Cdecl(n1 As Any Ptr,n2 As Any Ptr) As Long
    Return (*Cptr(long Ptr,n1)) - (*Cptr(long Ptr,n2))
End Function

Sub sort(s() As long)  
    qsort( @s(Lbound(s)),(Ubound(s)-Lbound(s)+1),Sizeof(s),@callback)
End Sub

'standard
Sub QuickSort(array() As long,begin As long,Finish As long)
    Dim As long i=begin,j=finish 
    Dim As long x =array(((I+J)\2))
    While  I <= J
        While array(I) < X
            I+=1
        Wend
        While array(J) > X
            J-=1
        Wend
        If I<=J Then
            Swap array(I),array(J)
            I+=1
            J-=1
        End If
    Wend
    If J > begin Then QuickSort(array(),begin,J)
    If I < Finish Then QuickSort(array(),I,Finish)
End Sub

dim as long limit=10000000
redim as long f(1 to limit)
randomize 1
for n as long=lbound(f) to ubound(f)
    f(n)=rnd*1000000-rnd*1000000
next
print "please wait"
dim as double t=timer
sort(f())
print timer-t;"   seconds  to sort (C qsort)  ";limit;"   integers,  press a key"
sleep
dim as string s
'show some
for n as long=lbound(f) to 100
   s+=str(n) + "  "+ str(f(n))+chr(10)
next
for n as long=1 to 5
s+="..."+chr(10)
next n
for n as long=ubound(f)-100 to ubound(f)
   s+=str(n) + "  "+ str(f(n))+chr(10)
next
print s
print "press a key"
sleep
'=============================================== standard quicksort =========
print "please wait"
'Do again
randomize 1
for n as long=lbound(f) to ubound(f)
    f(n)=rnd*1000000-rnd*1000000
next

t=timer
quicksort(f(),lbound(f),ubound(f))
print timer-t;"   seconds  to sort (Quicksort)  ";limit;"   integers,  press a key"
sleep
s=""
'show some
for n as long=lbound(f) to 100
   s+=str(n) + "  "+ str(f(n))+chr(10)
next
for n as long=1 to 5
s+="..."+chr(10)
next n
for n as long=ubound(f)-100 to ubound(f)
   s+=str(n) + "  "+ str(f(n))+chr(10)
next
print s
print "press a key"
sleep

 

[jj2007]

Chuckle sort is the true name, but I abbreviated for brevity.

Scottish humour ;-)

Code: Select all

for n as long=lbound(f) to ubound(f)
    f(n)=rnd*40000000-rnd*40000000
next

Crashes for bigger numbers, such as f(n)=rnd*50000000-rnd*50000000.

Here are results for the C vs QuickSort comparison, on a Core i5:

Code: Select all

please wait
 2.480924178207658   seconds  to sort (C qsort)   10000000   integers,  press a key
1  -999876
2  -999762
...
9999999  999364
10000000  999539

 1.846157761866834   seconds  to sort (Quicksort)   10000000   integers,  press a key
1  -999876
2  -999762
...
9999999  999364
10000000  999539

[dodicat]

I notice that the C sort is not recursive:

https://code.woboq.org/userspace/glibc/ ... ort.c.html

Which is a bonus.


I can manage, on chuck
rnd*85000000-rnd*85000000
on 32 bit fbc
and double that on 64 bit.
But since the udt chuck has dynamic (re sizeable arrays), it is not located on the stack, and can eat some page file if you make the range too large, or just crash on 32 bit fbc.

[caseih]

I've not analyzed this sort function, but it almost appears to me to be a variant on the Radix Sort. A Radix sort is O(n*m) where n is the number of elements to sort and m is the number of digits/bits/whatever in the number. If this is a variant on the radix sort, it is definitely linear time, so it will outperform qsort for some kinds of data.

Talking about wall clock speed of these sorting algorithms isn't nearly as useful as comparing the big O runtime.

[jj2007]

I've not analyzed this sort function, but it almost appears to me to be a variant on the Radix Sort. A Radix sort is O(n*m) where n is the number of elements to sort and m is the number of digits/bits/whatever in the number. If this is a variant on the radix sort, it is definitely linear time, so it will outperform qsort for some kinds of data.

One problem here is that "table sort" is not a widely accepted terminology. There is a Table Sort Example, and there is table.sort at MSDN, but both have apparently nothing to do with sorting an array of integers. Correct me if I am wrong.

According to SOF: What algorithm does table.sort use?, Lua's "table sort" is a quicksort. ArraySort() is an in-place radix sort, and it does indeed outperform the crt quicksort for, well, not so big integers. Since dodicat's "table sort" seems very memory hungry, the range of values seems to be a limiting factor. In contrast, ArraySort has no size problems, even QWORD (or double) arrays can be sorted. It just gets a little slower with increasing ranges.

Maybe dodicat can enlighten us about his "table sort" logic when he has finished chuckling.

[dodicat]

There is no sorting in the chucksort.
Five numbers
-23433,400,-32,1000,2

create an array to hold these values.
d(-23433)=-23433
d(400)=400
d(-32)=-32
d(1000)=1000
d(2)=2

and
in each case
repeat(-23433)=1
repeat(400)=1
...
...


The array is now in memory, and in ascending order.
d(-23433)=-23433
d(-23432)=0
d(-234331)=0
...
...
d(-32)=-32
d(-31)=0
...
...
with repeat(-23432)=0, repeat(-23431)=0 etc

if you had a repeat , say -32 again, then
repeat(-32)=repeat(-32)+1 (and d(-32) still remains -32 of course).
So you have all the array values in ascending order in memory and all repeats are recorded.
Just transfer these values back to the original array, exit the sub thus freeing the memory.

I suppose in a way, it is a sort of ordered array compressing, where the word sort here is not used in any chuckle kind of way.

[jj2007]

Thanks, dodicat. It resembles the radix and bucket "sort" algos. The question is perhaps how useful it can be in real life applications; you need to allocate an array of (maxrange-minrange)*sizeof integer bytes. But for limited ranges it is indeed very fast.

[caseih]

One could argue that chuck sort is a type of simple hashing algorithm. And hashing is something that's used in the real world all the time.