Since I got this code working, I thought it might find usefulness to some.
It's a Radix sorting routine, pretty capable, and very fast. It should be adaptable without too much trouble, and code comments are abundant =)
''Radix sorting routine, written Aug 21st 2006 by Chris G.(Blitz_Amateur/DBF)
'
'Feel free to use in your own work with our without credit, I made this for fun,
'and I thought a few people might find use for it =)
'
'For a description of a radix sort, visit:
'http://en.wikipedia.org/wiki/Radix_sort
OPTION EXPLICIT
'Maximum amount of numbers that can be sorted.
'At 100000, the routine requires approx 5MB free memory
const MaxNumbers = 100000
'Declare the RadixSort function
declare function RadixSort(byval array as integer pointer, byval total_length as integer)
'Define Array pointers for storing numbers during sort
'Each of the arrays allocated below represents a bank for storing numbers in
'which the digits we are reading fit.
dim shared as integer pointer q1,q2,q3,q4,q5,q6,q7,q8,q9,q0,q(10)
q0 = callocate(MaxNumbers+1, Len(integer))
q1 = callocate(MaxNumbers+1, Len(integer))
q2 = callocate(MaxNumbers+1, Len(integer))
q3 = callocate(MaxNumbers+1, Len(integer))
q4 = callocate(MaxNumbers+1, Len(integer))
q5 = callocate(MaxNumbers+1, Len(integer))
q6 = callocate(MaxNumbers+1, Len(integer))
q7 = callocate(MaxNumbers+1, Len(integer))
q8 = callocate(MaxNumbers+1, Len(integer))
q9 = callocate(MaxNumbers+1, Len(integer))
'Set up one array to store pointers to other arrays
q(0) = q0
q(1) = q1
q(2) = q2
q(3) = q3
q(4) = q4
q(5) = q5
q(6) = q6
q(7) = q7
q(8) = q8
q(9) = q9
randomize timer ' Seed randomizer
'Setup vaiables
dim as integer pointer myvals ' Numbers array
dim as integer length, i ' Length: amount of numbers to be sorted i: loop var
dim as double ttime ' Used to calculate time
dim as double toprange ' Maximum value for the random numbers in array
'===============================================================
length = 99000 ' Amount of numbers to sort
toprange = 99999 ' Highest possible value
'===============================================================
myvals = callocate(length,len(integer)) ' Allocate memory for array of numbers
' Add random number to array inside specified range
for i=0 to length-1
myvals[i] = rnd*toprange
next
ttime=timer ' Start of timer for FPS calc
i = RadixSort(myvals,length-1) ' Sort numbers, store return value to error check
ttime = timer-ttime ' The rest of FPS calc
'Error checking
if i = -1 then
' If errors, inform user, and quit
Print "Failed to sort, too many numbers"
goto 1
end if
' Write results to file
open "sorted.txt" for output as #1 ' Open file
' Write array to file
for i=0 to length-1
print #1,myvals[i]
next
close #1 ' Close file
print 1.0/ttime ' Print estimated FPS for the sorting routine
1 ' Goto line for ending on error
'Wait for ESC to quit
do
loop until inkey$ = chr(27)
for i=0 to 9
deallocate q(i)
next
deallocate myvals
'Radix Sorting Function
'Parameters:
'
'ar: pointer to array of values to sort
'
't: total number of values to sort
'
function RadixSort(byval ar as integer pointer, byval t as integer)
if t > MaxNumbers then return -1 ' If too many numbers, exit sorter
'Declare variables for loops and temporary storage
dim as integer i,temp,i2,num
dim as single m
dim as byte done
m = 1 ' Multiplier of ten
done = 0 ' Tells us when we're done sorting
num = 0 ' Used at the end to put numbers back in the array in the correct order
'Sorting Loop
do
done = 1 ' Set done to 1
'Loop through the array of numbers
for i=0 to t
'Get the digit for the curret power of ten
'If there is no digit for the current power of ten, this returns 0
temp = cint((ar[i]/m)-0.49) mod 10
'If any of the digits are non-zero, then the loop will continue.
'When there are no more digits for the current power of ten
'the loop will exit, because the sorting is complete.
'This next line actually checks forward for zero-digits.
'If we run into a zero, it obviously won't have a second digit, so
'this returns a zero anyway. Doing this saves us one run through the
'array.
if cint((ar[i]/(m*10))-0.49) <> 0 then done = 0
'We keep the number of values in a bank stored in the first element
'So, we need to update that number
q(temp)[0] += 1
'And after updating the number of values, we will assign our current
'value ot the bank in which it belongs
q(temp)[q(temp)[0]] = ar[i]
next
num=0 'This controls the position in the original array
'Loop through our number banks
for i=0 to 9
'Go through the elements stored in the bank
for i2=1 to q(i)[0]
'Assign those elements to the original array
ar[num] = q(i)[i2]
'Increment the position in the original array
num=num+1
next
'Now that we've gotten all the values we need from this bank, reset
'the number of stored elements to zero.
'We don't clear this bank because all fo teh data we'll read next
'time around will be written over.
q(i)[0] = 0
next
'Increase to the next power of ten, check for an ESC press (security measure)
'And repeat loop unless we're done.
m*=10
if inkey = chr(27) then done = 1
loop until done = 1
End Function
