Number Sort Algorithm

[T.Jackson]

Number sorting algo that I spat out yesterday can sort 10,000 64 BIT numbers in 15 seconds on a PIII 866MHz. Considering the simplicity of it - this is fast! The code is in Visual Basic but shouldn't be too hard to port to PBP. I don't have time to do it at the moment, anyone up for it? If you feel that you have an even better solution, please post it here.

Private Function Sort_Numbers(ByRef Num_Array)

   ' (An easy to get your head around algo)
   
   Dim Compare_A As Long
   Dim Compare_B As Long
   Dim Swap As Long
   Dim Array_Pos As Long
   Dim i As Long
   Dim j As Long
   Dim k As Long
   
   i = UBound(Num_Array)                 ' Size / last index of array
   k = i                                 ' Copy of i used to show progress - indexes sorted thus far
   
   Do Until i = 0                        ' Loop until entire list has been sorted
      Compare_A = Num_Array(i)           ' Load comparison var (starting at bottom of list)
      For j = Array_Pos To i             ' Try to find a bigger num (starting from top of list)
         Compare_B = Num_Array(j)        '
         If Compare_B > Compare_A Then   ' This num bigger?
            Swap = Num_Array(i)          ' Swap them
            Num_Array(i) = Compare_B     '
            Num_Array(j) = Swap
            Array_Pos = j                '
            Exit For                     ' Bail out, but we need to come back (might be an even bigger num)
         End If
      Next
      If j > i Then                      ' Num is in correct pos - nothing bigger exists
         i = i - 1                       ' Move to next index
         Array_Pos = 0
         
         ' Show user how many have been sorted so far (yes this will slow things down marginally)
         Progress = "Sorted " & (k - i) & " numbers"
         DoEvents
      End If
   Loop
   
End Function

[T.Jackson]

As you can see from the screen grab below, it sorted 1,000 numbers in 697mS. This figure starts to badly degrade with more than 1,000.

<img src="http://www.picbasic.co.uk/forum/attachment.php?attachmentid=1872&stc=1&d=118498310 3">

[T.Jackson]

Will it sort a million numbers? - Yes it will. In around an estimated 131.94 hours that is. Divide that figure by bout 10 for a really fast modern PC. Maybe even more for a quad core. Happy sorting!

[Melanie]

Let's swing sorting slightly towards PBP... not quite a million numbers though... can't recall too many PICs with that kind of RAM capability, and with other forms of storage you're then relying on their I/O speed characteristics.

However, in professional embedded applications, when you take an ADC reading, good practice states that you take more than one and eradicate any anomalies. That way, when your sensor sits at the end of a length of cable, you can eliminate lightning strikes and the odd Redneck trying to weld his pickup truck in near proximity.

Well, the way I achieve that is to take say 16 ADC readings, sort them in sequential order of value, junk the top and bottom four readings as being 'out-of-range', sum and average the middle eight... this makes ADC readings in industrial applications pretty much bomb-proof...

Now, whilst there's quite a few tricks and treats within this, here's a simple sort routine for doing just that (when you analyse it, it's pretty similar to your example Trent albeit a little more compact)... The Data to be sorted sits in an array called RawData, and when it falls out of the subroutine, RawData is in sequential order. Change DataA and RawData variables to WORDS if you need them. Those that know will notice that the additional variable DataA is only needed because PBP's SWAP command doesn't work with arrays.

    CounterA var Byte
    DataA var Byte
    RawData var Byte [16]
    .. ..

        '
        '    Sort Array
        '    ----------
SortArray:
    CounterA=0
SortLoop:
    If RawData(CounterA+1) < RawData(CounterA) then
        DataA=RawData(CounterA)
        RawData(CounterA)=RawData(CounterA+1)
        RawData(CounterA+1+0)=DataA
        If CounterA > 0 then CounterA=CounterA-2
        endif
    CounterA=CounterA+1
    If CounterA < 15 then goto SortLoop
    Return

[T.Jackson]

RawData(CounterA+1+0)=DataA

+ 0 ?

*Like the multiple sample theory - something I never really thought about. But then again, I'm not an engineer.

[Melanie]

Yes, +0, other than Bruce, Darrel (and perhaps Mister_E), who on this forum knows why?

[Ioannis]

...Those that know will notice that the additional variable DataA is only needed because PBP's SWAP command doesn't work with arrays.

Well, there is a way to swap two variables without the need of a third dummy one:

a=a^b
b=a^b
a=a^b

If you test it with binary numbers be surprised that finally there is swap without dummy!

Ioannis

[Darrel Taylor]

Cool.

And I suppose if someone wanted to test the "Surprise", they might do something like this ...

;Initialize your hardware first

A      VAR WORD
B      VAR WORD
TempA  VAR WORD
TempB  VAR WORD

LCDOUT $FE,1

For A = 0 to 65535
    LCDOUT $FE,2,"A=",DEC A
    For B = 0 to 65535
        TempA = A
        TempB = B
        TempA = TempA ^ TempB
        TempB = TempA ^ TempB
        TempA = TempA ^ TempB
        IF (TempA <> B) OR (TempB <> A) THEN ; Test Failed
            LCDOUT $FE,1,"Test Failed",$FE,$C0,"A=",DEC A,", B =",DEC B
            STOP
        ENDIF
    Next B
Next A

LCDOUT $FE,1,"Test Passed!"
STOP

Then some 40 hours later (@ 20Mhz) [that's over 4 billion combinations],
you would no doubt see the message "Test Passed!" on the LCD.

Only a half hour into it, but it's still passing. Kinda obvious what the result will be.

Update: 43hrs, Test Passed! (obviously)
<br>