Number Sort Algorithm

[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?

[T.Jackson]

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.

[Melanie]

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.

[T.Jackson]

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.

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

[Ioannis]

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

Ioannis

[Darrel Taylor]

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>

[Darrel Taylor]

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

[Bruce]

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.