I was trying to code Quicksort in Python (see the full code at the end of the question) and in the partition function I am supposed to swap two elements of an array (call it x). I am using the following code for swapping based on the xor operator:
x[i]^=x[j]
x[j]^=x[i]
x[i]^=x[j]
I know that it should work because of the nilpotence of the xor operator (i.e. x^x=0) and I have done it like a million times in Java and in C without any problem. My question is: why doesn’t it work in Python? It seems that it is not working when x[i] == x[j] (maybe i = j?).
x = [2,4,3,5,2,5,46,2,5,6,2,5]
print x
def part(a,b):
global x
i = a
for j in range(a,b):
if x[j]<=x[b]:
x[i]^=x[j]#t = x[i]
x[j]^=x[i]#x[i] = x[j]
x[i]^=x[j]#x[j]=t
i = i+1
r = x[i]
x[i]=x[b]
x[b]=r
return i
def quick(y,z):
if z-y<=0:
return
p = part(y,z)
quick(y,p-1)
quick(p+1,z)
quick(0,len(x)-1)
print x
As to why it doesn't work, it really shouldn't matter1, because you shouldn't be using code like that in the first place, especially when Python gives you a perfectly good 'atomic swap' capability:
x[i], x[j] = x[j], x[i]
It's always been my opinion that all programs should be initially optimised for readability first and only have performance or storage improvements imposed if there's a clear need and a clear benefit (neither of which I've ever seen for the XOR trick outside some incredibly small data environments like some embedded systems).
Even in languages that don't provide that nifty feature, it's more readable and probably faster to use a temporary variable:
tmp = x[i]
x[i] = x[j]
x[j] = tmp
1 However, if you really want to know why it's not working, it's because that trick is okay for swapping two distinct variables, but not so well when you use it with the same variable, which is what you'll be doing when you try to swap x[i] with x[j] when i is equal to j.
It's functionally equivalent to the following, with print statements added so you can see where the whole thing falls apart:
>>> a = 42
>>> a ^= a ; print(a)
0
>>> a ^= a ; print(a)
0
>>> a ^= a ; print(a)
0
Contrast that with two distinct variables, which works okay:
>>> a = 314159; b = 271828; print(a,b)
314159 271828
>>> a ^= b; print(a,b)
61179 271828
>>> b ^= a; print(a,b)
61179 314159
>>> a ^= b; print(a,b)
271828 314159
The problem is that the trick works by transferring information between the two variables gradually (similar to the fox/goose/beans puzzle). When it's the same variable, the first step doesn't so much transfer information as it does destroy it.
Both Python's 'atomic swap' and use of a temporary variable will avoid this problem completely.