Number Sort Algorithm

1. ## Number Sort Algorithm

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.

Code:
```Private Function Sort_Numbers(ByRef Num_Array)

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```

2. ## Screen Grab

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">

3. ## One Million Numbers!

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!

4. ## Sorting Numbers

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.

Code:
```    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```
Last edited by ScaleRobotics; - 2nd July 2010 at 17:35.

5. 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.

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

7. Originally Posted by Melanie
...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

8. Cool.

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

Code:
```;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>
Last edited by Darrel Taylor; - 27th July 2007 at 08:26. Reason: Final result

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts