Syfu_H - 1 year ago 99
C++ Question

bubble sort with xor or temp

in a scenario of sorting an array using bubble sort algorithm which is more effective creating a temporary variable inside nested-loop or using xor operator:

``````#include <iostream>

int main()
{
int array[5] = {7, 2, 5, 3, 4};

/*1: using temporary variable

for(int i(0); i < 5; i++)
{
for(int j(i + 1); j < 5; j++)
{
if(array[i] > array[j])
{
int tmp  = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
*/

//2: using xor ^ swapper
for(int i = 0; i < 5; i++)
{
for(int j(i + 1); j < 5; j++)
{
if(array[i] > array[j])
{
array[i] ^= array[j];
array[j] ^= array[i];
array[i] ^= array[j];
}
}
}

for( i = 0; i < 5; i++)
std::cout << array[i] << ", ";

std::cout << std::endl;
return 0;
}
``````

I only want to know which is quicker and more powerful knowing that the two methods work fine.

As others have already pointed out, the only way to know for sure is to measure it.

"how to measure it?" would have been the subject of an altogether different question, if such a question was on-topic on stackoverflow. But it isn't.

Google is your friend. Google it. Look for keywords such as "benchmark" or "profile" together with "C++" and perhaps the name of the IDE you are using.

Aside from that, I can give you some pretty good indication as to which one will be faster by just examining the instructions.

The instruction sequence

``````  a ^= b;
b ^= a;
a ^= b;
``````

translates into the following unoptimized instructions:

``````  load  register from a            ;memory reference
xor   register with b            ;memory reference
store register to a              ;memory reference
load  register from b            ;memory reference
xor   register with a            ;memory reference
store register to b              ;memory reference
load  register from a            ;memory reference
xor   register with b            ;memory reference
store register to a              ;memory reference
``````

which are likely optimizable as follows:

``````  load  register1 from a           ;memory reference
load  register2 from b           ;memory reference
xor register1 with register2
xor register2 with register1
xor register1 with register2
store register1 to a             ;memory reference
store register2 to b             ;memory reference
``````

The instruction sequence

``````  int tmp  = a;
a = b;
b = tmp;
``````

translates into the following unoptimized instructions:

``````  load  register from a            ;memory reference
store register to tmp            ;memory reference
load  register from b            ;memory reference
store register to a              ;memory reference
load  register from tmp          ;memory reference
store register to b              ;memory reference
``````

which are likely optimizable as follows:

``````  load register1 from a            ;memory reference
load register2 from b            ;memory reference
store register1 to b             ;memory reference
store register2 to a             ;memory reference
``````

As you can see, both optimized fragments only involve four memory references, so the two approaches are roughly equal, but the XOR approach involves 3 extra instructions, so it cannot possibly perform better.

Don't believe me? Well then, don't take my word for it! I cannot even be sure what kinds of additional optimizations your compiler may be capable of performing. So, besides running a benchmark or profiling the code, try also seeing the assembly produced by your compiler for the above fragments of code. (With all optimizations enabled, of course.)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download