Syfu_H Syfu_H - 2 months ago 9
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.

Answer

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