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. I normally have the ability to at least come up with some sort of opinion with most things (often it's wrong), but on that, I can't even think of one guess, not even an obviously far-fetched one.

8. Going back to the early days of PBP, before Microcode studio, to the days when you carved your code into slate tablets, there was an anomaly/bug with PBP sometimes handling math within array parenthesis. The workaround was to simply add a dummy argument (which goes to show how old that code is). Now I can't remember at which point the error was eradicated without compiling a bunch of test samples across more than half-a-dozen versions of PBP. The code I posted above pretty much works with all versions, though if absolute speed is your thing, you can probably lose the +0 if your PBP is relatively up-to-date.

9. Oh! - well that puts my mind at ease, it's things like that keep me from getting a good nights sleep. I'll be able to switch off tonight and get some rest.

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

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

12. Nice routine Darrel! 40 hours to wait for "Test Passed!", wow!

Ioannis

13. LOL,

I think I'll need those 40 hrs. just to wrap my head around why it works.

It does work, but the explanation eludes me.

@ Don't tell me, I've still got 38 hrs to go
<br>

14. Programs still running, but I think I got the XOR thing figured out.
Not that I could explain it though.

Practicing my Flash at the same time

.. Flash moved down ..

15. How this logic works is pretty cool. I saw this on the PIClist a few years back.

Here's how it works.

a VAR BYTE
b VAR BYTE
a = %11001100
b = %00110011

a=a^b ' a now = %11001100 ^ %00110011 which = %11111111

1 ^ 0 = 1. 1 ^ 1 = 0. 0 ^ 0 = 0.

b=a^b ' b now = %11111111 ^ %00110011 which = %11001100 (value of original a)

b now contains the original value of a.

a=a^b ' a now = \$11111111 ^ %11001100 which = %00110011 (value of orignal b)

Now that b = the original value held in a, ^-oring a with b returns the orignal
value of b, in a.

Using any two values, it still works the same. Like this;

a = %11011100
b = %00110011

a=a^b ' a now = %11011100 ^ %00110011 which = %11101111
b=a^b ' b now = %11101111 ^ %00110011 which = %11011100 (value of original a)
a=a^b ' a now = \$11101111 ^ %11011100 which = %00110011 (value of orignal b)

Pretty nifty way of swapping variables.
Last edited by Bruce; - 25th July 2007 at 22:16.

16. And is as fast as using swap technique!

I was wondering where I first read about it and after alot of searching, it was on a summer double Elektor issue.

Ioannis

17. Ioannis,

Thanks for the interesting idea to ponder.

And thanks for the extra examples Bruce. But while it does show that it gets from A to B and visa versa, it didn't really answer the Why? that had me so baffeled. When I get baffeled I usually become obsessed at figuring out the why, especially when it seems like it should be so simple (Like 3 XOR's in a row).

My biggest problem was thinking it was combining the bits with the first A=A^B, then somehow pulling the bits back out with the next XOR. But none of that was making any sense.

After making the Flash, I realized that the XOR gate should really be called the "They're Different" gate, which is what the XOR does. If both inputs are the same the output is 0, if they're different, the output is 1.

Then it all made perfect sense.

The first A = A^B determines if both bits are Different or not, and stores it back in A.

Since you still know the original B value, and you know if the 2 are different then ...

If B = 1 and "They are Different" then A used to be = 0, which accounts for the B = A^B

The last A = A^B does the same thing. If they are different, and you know the new B is a 0, then the new A has to be a 1.

<OBJECT CLASSID= "clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" WIDTH="600" HEIGHT="300" CODEBASE="http://active.macromedia.com/flash5/cabs/swflash.cab#version=5,0,0,0"><PARAM NAME="MOVIE" VALUE="http://www.pbpgroup.com/files/XOR.swf"><PARAM NAME="PLAY" VALUE="true"><PARAM NAME="LOOP" VALUE="true"><PARAM NAME="WMODE" VALUE="opaque"><PARAM NAME="QUALITY" VALUE="high"><EMBED SRC="http://www.pbpgroup.com/files/XOR.swf" WIDTH="600" HEIGHT="300" PLAY="true" LOOP="true" WMODE="opaque" QUALITY="high" PLUGINSPAGE="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash"></EMBED></OBJECT>

I feel better now.
<br>

18. Cool Darrel!

But what is buzzing me more, is how one can think about it in the first place. He/she must be really clever one. So simple, so clever!

Ioannis
Last edited by Ioannis; - 13th May 2015 at 08:51.

19. I've found a few nifty tricks like this on the Microchip forum in the Tips &
Tricks section http://forum.microchip.com/tm.aspx?m=165770

Really gets one to thinking.

The PIClist is another good resource, but the signal-to-noise ratio there can
be pretty high.

Nice job on the Flash XOR gate Darrel...;o}

20. Thank you, thank you,

So now that I've proven to myself that it works, ...
back to the topic ...

I think that changes Melanie's Sort from Post #4, to ...
Code:
```	CounterA var Byte
RawData var Byte [16]
.. ..

'
'	Sort Array
'	----------
SortArray:
CounterA=0
SortLoop:
If RawData(CounterA+1) < RawData(CounterA) then
RawData(CounterA)     = RawData(CounterA) ^ RawData(CounterA+1)
RawData(CounterA+1+0) = RawData(CounterA) ^ RawData(CounterA+1)
RawData(CounterA)     = RawData(CounterA) ^ RawData(CounterA+1)
If CounterA > 0 then CounterA=CounterA-2
endif
CounterA=CounterA+1
If CounterA < 15 then goto SortLoop
Return```
Now I've got to wonder if it makes any difference?

edit: The added array operations would probably even slow it down.
<br>
Last edited by Darrel Taylor; - 26th July 2007 at 14:07. Reason: .

21. The one thing for sure is that code will use one variable less.

As for speed, I don't know. Operation either on swap or with the XOR thing i believe are the same...

Ioannis

22. You know, if you say Super-cala-fragile-listic-expealidoius, backwards, at exactly 3:03 am, the Blair Witch will appear before you and grant you with exactly one wish. Be careful what you wish for though.

23. Originally Posted by T.Jackson
You know, if you say Super-cala-fragile-listic-expealidoius, backwards, at exactly 3:03 am, the Blair Witch will appear before you and grant you with exactly one wish. Be careful what you wish for though.
Didn't that was said by Mary Poppins? Iliked it a lot!

But how does this connect with the above? Sorry I cannot understand, as english is second language to me.

Ioannis

24. It doesn't work (because Trent forgot to use his spellchecker)... I'm worried about the 'fragile' section in the middle of the word...

25. and needs an 'c' in expealidoius like: expealidocius

Ioannis

26. The biggest problem is that it takes longer than a second to say it.

There's no way to say the whole thing at exactly 3:03 am.

But backwards (according to the movie) would be.
dociousaliexpiisticfragilcalirupus

docious-ali-expi-istic-fragil-cali-rupus
<br>

27. Legend has it that if you stand in front of a mirror, any time past midnight, and say three times; "I don't believe in the Bell Witch" - the next morning you will wakeup with finger nail scratches on your cheek.

28. Do you have any more of those pills?

And, can I have some??
<br>

29. That legend is for real Darrel.

30. > next morning you will wakeup with finger nail scratches on your cheek.

... and there I was wondering why I never get dated more than once!

31. ## how does it work?

Hello.
I apologize for reviving old thread but forum is already crowded with so many topics I don't want to aggrandize it further.

In mrs. Melanie's routine I don't understand the following:
Code:
```SortArray:
...
IF CounterA>0 then CounterA=CounterA-2
...
CounterA=CounterA+1
IF CounterA<15 THEN SortArray```
As I see it, after the first pass through the loop CounterA is 1, so when it hits IF CounterA>0... wouldn't that make CounterA bigger than15 and exit the loop (CounterA war byte so 1-2=255)?
Can someone please explain it to me?

32. >Mrs Melanie!

Don't marry me off yet - I'm having way too much fun being single!

This is a SWAP SORT routine with an Array of 16 elements... (this version is in ASCENDING order, ie the smallest value will end up in RawData(0) and the largest value will end up RawData(15).

First time through the loop CounterA=0 (not 1 as you stated).

You compare RawData(1) with RawData(0) and if RawData(1) is smaller you swap them (NOT if it's bigger or if is the same).

There was an ARRAY BUG in PBP V2.42, which caused problems with Array manipulation - for example RawData(CounterA+1), the workaround (before MeLabs fixed it) was to add a dummy proceedure, so this became RawData(CounterA+1+0). This BUG has long been fixed, so you don't actually need the +0 bit nowadays.

Only if you are NOT at the start of the Array Sort (ie CounterA>0) do you then go back and look at the previous set of Array elements and compare those again (because you've just swapped the upper one of them). You actually subtract 2, because the very next step adds one, so in essence you only go back one Array step. If you are already at the beginning of the Array (ie CounterA=0), you DON'T step back, because that will cause you to step outside your array limits, so you move forward by adding 1 to CounterA.

You repeat the process until you've scanned the whole array and CounterA=15 (your upper Array limit).

Whether you SWAP or NOT, if CounterA=0 then the -2 will never happen, you can only move FORWARDS to CounterA=1 (ie CounterA=CounterA+1).

If CounterA=1, then if you DON'T Swap, you move FORWARDS (as above), but if you DO SWAP then CounterA will move BACK by ONE Count (ie CounterA=-2+1), which if CounterA was 1 to start with, it will now move back to be Zero.

33. Don't marry me off yet - I'm having way too much fun being single!
Please accept my apology, English is not my native language so I make many mistakes.

Thank you very much for your kind and patient response. Now I see how stupid my question really was. I grasped on CounterA+1 & CounterA-2 as a bull on red flag therefore completely dropping the rest out of my sight. I'll put more effort next time instead of bothering with a silliness.
Thanks again for the explanation, as well for sharing the routine.

Kind regards

34. *smiles* No appologies are required!

Doesn't matter about asking questions - that is what this forum is here for, everyone who reads learns something from them.

35. 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...
Miss Melanie, in doing so you are potentially junking good data, but you can also potentially retain and use in your mean bad data, since you have no way to know how many bad readings you will take with your sampling.

A statistically correct approch should be to calculate the mean and the standard deviation (sd), of all your 16 readings, than retain all data within +/- 1 or 2 sd depending esclusively on your need.

A simpler approach could be to decide which threshold (in percentage of the mean) to apply to reduce the variance, than take the mean of all the 16 readings and discard all the data beyond the threshold limit.

In both cases you will not need to sort your array.

Al.
Last edited by aratti; - 8th November 2009 at 17:53.

36. But the maths to do those calculations I feel are more code hungry than just sorting...

Ioannis

37. Ioannis, if the number that you will display has no importance then you can fix it with a constant, display will be rock stable (always the same number). On the other hand, if the number should provide you usefull information then you must treat it in such a way to preserve those information, which means you must use the correct statistical approch, regardless how code hungry the algorithm could be.

Al.
Last edited by aratti; - 9th November 2009 at 09:47.

38. Of course I agree with you Al.

I just feel that Melanies approach is faster giving almost same result for most cases.

Sure if you need the most precise results, one in the way to follow.

Ioannis

39. There are many ways of accomplishing the same task. Give that task to a dozen engineers, you may get a dozen different approaches, each achieving the desired result, and each achieving that result with different methodology. Really, in electronics and programming there is no SINGLE correct way of doing anything and the methodology you employ rests with your imagination which makes our business just as exciting and creative as any Artist painting a canvas.

If I am measuring ambient temperature for example, I don't expect to take sixteen readings 50uS apart and discover twelve of them to measure around +22.7 Celcius, one to measure -20, one measures -40 Celcius, one measures +400 and one measures +700 Celcius. But that is exactly the kind of result you might get is you experience a local lightning strike with spikes being induced into your electronics. Very short bursts of total rubbish.

Now using a conventional method of summation would produce an erroneous result, but the temperature may well drop to -20 or minus 40 in winter, so that could also be technically valid data, but in the case above, we know that the onset of winter doesn't happen in 100uS, so we need to trash the data at the extreemes (even if it might be good data).

Now in the code I published some years back, I put forward an idea of taking multiple samples, sorting them, discarding those results at the fringes and concentrating only on the centre median of our collection of data. This works good in the majority of industrial and environmental applications and even for motion control on an industrial assembly robot (filtering localised welding spikes). The amount of data you discard is not arbitrary, it depends on the number of samples you've taken and the TIME you've sampled them across. I know lightning tends to be short duration spikes, so out of a milliseconds worth of sampling, I know that anything out of the ordinary lasting 50 or 100uS we can happilly junk. But, if I was creating the firmware for a new Digital Oscilloscope or sampling an Audio waveform for an Amplifier, this would obviously not be the correct approach.

40. Hi Darrel, I tested the sorting snippet you have posted, using a rather interesting swapping technique.

The code worked, but now and than, it was yielding very fanny results.

From a closer code analysis, I came to the conclusion that :

Code:
`If CounterA > 0 then CounterA=CounterA-2`
should be corrected with:

Code:
`If CounterA > 1 then CounterA=CounterA-2`
After the correction, I didn't see any fanny result for the rest of my testing period.

The explanation I have given is the following:

If CounterA = 1 then CounterA - 2 = 255 and this screw up everything.

Can you confirm?

Al.
Last edited by aratti; - 19th December 2009 at 18:14.

#### Posting Permissions

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