Number Sort Algorithm

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

[Ioannis]

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