Number Sort Algorithm

[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

[Darrel Taylor]

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>

[Ioannis]

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

[Bruce]

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}

[Darrel Taylor]

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

	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>

[Ioannis]

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

[kenif]

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

	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>

This sort just saved my butt, thank you.
As the PICs get faster, speed is less of a consideration.