Friday, 11 November 2011

Swapping elements in an array without a temporary variable

The common idiom to swap two elements in an array is to use a temporary variable that is consequently pushed on the stack, which looks like the following:

int[] elements = {1,2,3,4,5,6,7,8,9,10}
int tmp = elements[0];
elements[0] = elements[9];
elements[9] = tmp;


In that example I was swapping the first and last elements. However this is not the most optimized way as the elements can be swapped without that temporary variable being created.

In true blue peter style, here's one I created earlier:

elements[0] = elements[0]^[elements[9];
elements[9] = elements[0]^[elements[9];
elements[0] = elements[0]^[elements[9];


It works in the same way that algebra works, where equality can be changed w.r.t the variable.

a = b - c
b = a + c
c = b - a


The bitwise operators only work on integers and not all real numbers (more speficially, floating point numbers) so the arithmetic operators must be used instead to swap real numbers in an array:

float[] data = {1.1f, 2.234f, 4.5454f, 1.110f, 9.999f, 3.1562f};
data[0] = data[0] - data[5];
data[0] = data[5] + data[0];
data[5] = data[0] - data[5];


Using these algorithms will provide micro-optimization but at the expense of clarity.

No comments:

Post a Comment