Swapping

If you have done any type of Computer Science course during your education you will probably have had to write some sort of sorting algorithm. The premise of a good sorting algoirthm is to define a sequence of swaps such that the minimum no. of swaps will be used to sort the array of elements. This I will take as read and discuss here how to make sure the swap itself is of minimal complexity. Now most of you will think that this is how to do the most efficient swap...

$temp = $A;
$A = $B;
$B = $temp;

... and to tell you the truth, so did I for about three years. Then, when in a Semantics of Programming lecture, we were proving that the above code really does swap every pair. I made some comment about if the semantics would be the same with non-destructive languages, which sent the lecturer off on a tangent proving that the following algorithm swaps every pair. Not only did he prove the correctness - he made a very suprising comment about the complexity too.

$A = $A ^ $B;
$B = $A ^ $B;
$A = $A ^ $B;

Not only do these swaps use a smaller space complexity, they also are more efficient as the entire operation can happen on the ALU. To the right is a diagram that explains what is going on here in terms of the circuitary. Of course, there is a similar procedure that uses arithmetic operations. Below is a test procedure written in PHP and results, demonstrating the speeds of the various methods on my LAMP stack. I'm sure you'll agree that this method is the superlative swap on this platform. However, for certain applications this can be dangerous to use if aliasing is used. See here for more on that.

function physical_swap(){
global $A,$B;
$temp = $A;
$A = $B;
$B = $temp;
}
function arithmetic_swap(){
global $A,$B;
$A = $A+$B;
$B = $A-$B;
$A = $A-$B;
}
function logical_swap(){
global $A,$B;
$A = $A ^ $B;
$B = $A ^ $B;
$A = $A ^ $B;
}

function time_test($func){
$mtime = microtime();
$mtime = explode(' ', $mtime);
$mtime = $mtime[1] + $mtime[0];
$starttime = $mtime;
call_user_func($func);
$mtime = microtime();
$mtime = explode(" ", $mtime);
$mtime = $mtime[1] + $mtime[0];
$endtime = $mtime;
return ($endtime - $starttime);
}

// Test
$A=0;
$B=1;
echo "A:$A B:$B<br />";
echo "Physical swap took: " . time_test("physical_swap") . "s to make...<br />";
echo "A:$A B:$B<br />";
echo "Arithmetic swap took: " . time_test("arithmetic_swap") . "s to make...<br />";
echo "A:$A B:$B<br />";
echo "Logical swap took: " . time_test("logical_swap") . "s to make...<br />";
echo "A:$A B:$B<br />";
?>