Procedure to swap values

[airowe]

I need to write a procedure that swaps the values of a and b if a is greater and otherwise leaves a and b unchanged.

Here is what I have so far:

#include<iostream>


using namespace std;

void sort(int &a, int &b)
{
if (a > b)
int temp = a;
a = b;
b = temp;
}

int main()
{
int u = 2;
int v = 3;
sort(u, v);
cout << "u=" << u << "v=" << v << endl;

system("pause");
return 0;
}

I keep getting an error message that temp is undeclared in the line "b = temp". Any idea why?

[hthapar]

put the condition of (a > b) in main rather than in swap(). Also I dont know why do you have references passed as parameters to the swap function. Just pass the values. This way only if your condition of (a>b) if satisfied in main, the control will go in the function swap( ).

[seymore15074]

An if statement will only execute 1 statement if the condition is true, unless you specify a block of statements using {}'s.

The pass by reference is fine, it will do exactly what you want once you add {}'s.

This is equivalent to your function at this point:

void sort(int &a, int &b)
{
    if (a > b)
    {
        int temp = a;
    }
    a = b;
    b = temp;
}

Once the block ends, temp goes out of scope. This is what the error message is telling you.

[airowe]

Thank you seymore. Knew it was something simple I was overlooking...

[seymore15074]

It always is. Glad to help out.

[Zaita]

Quicker way :) Without the use of a temp variable

void sort(int &a, int &b) {
 if (a > b) {
   a = a + b;
   b = a - b;
   a = a - b;
 }
}

[seymore15074]

Now that's clever; I have never seen that before! Nice post Zaita.

[guestgulkan]

That is very similar to the xor method.

[airowe]

How about to sort three variables in descending order? Would you need multiple if statements?

i.e.:

int temp = 0;

if (a > b)
{
temp = a;
a = b;
b = temp;
}

if (b > c)
{
temp = b;
b = c;
c = temp;
}
if (a > b)
{
temp = a;
a = b;
b = temp;
}

[mordekai]

This works just fine, but if you want to sort more numbers, you're gonna have to type a lot of if-statements. With n numbers there are n*(n-1)/2. So you should think about putting the numbers in an array and using a for-loop.

By the way. This kind of sorting is called bubble-sort.
http://en.wikipedia.org/wiki/Bubble_sort

[airowe]

Ah, the Bubble Sort. I remember this.

Thanks mordekai.

[airowe]

Zaita,

Your way without the temp variable wouldn't work here, huh?

http://www.cplusplus.com/reference/string/swap.html

[seymore15074]

I'd bet the STL is implemented using the temp variable approach so that it only requires the value_type to be Assignable. The solution posted would additionally require that the operators + and - be defined. It would work for integral types; maybe there should be a template specialization for that (actually, for all I know there might already be one).

[helios]

Zaita's method works only with numerical types (integers, floats, bignums, etc.).
But I kinda like the XOR version better, even if it only with integers:

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

The standard swap is just

template <typename T>
void swap(T &a,T &b){
    T temp=a;
    a=b;
    b=temp;
}

I doubt there's a template specialization.

[jsmith]

No because the add/sub trick and the xor trick are both slower than using a temporary. They'd only specialize to optimize.

[helios]

Really? It's slower? Even though in the past, people would zero by XORing something to itself?

[seymore15074]

Wikipedia says that most compilers can optimize away the temporary but the XOR swap must always be sequential and would not be optimized. Interesting!

[guestgulkan]

I suppose the temp variable method might well be faster:

In the interest of scientific research:
Here is the source:

  temp = a;
  a=b;
  b=temp;

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

and here is the resultant code:

1 2 3 4 5 6 7 8 9 10 11 12

19: temp = a; 004114EC 8B 45 F8 mov eax,dword ptr [a] 004114EF 89 45 E0 mov dword ptr [temp],eax 20: a=b; 004114F2 8B 45 EC mov eax,dword ptr [b] 004114F5 89 45 F8 mov dword ptr [a],eax 21: b=temp; 004114F8 8B 45 E0 mov eax,dword ptr [temp] 004114FB 89 45 EC mov dword ptr [b],eax 22:

23: a^=b; 004114FE 8B 45 F8 mov eax,dword ptr [a] 00411501 33 45 EC xor eax,dword ptr [b] 00411504 89 45 F8 mov dword ptr [a],eax 24: b^=a; 00411507 8B 45 EC mov eax,dword ptr [b] 0041150A 33 45 F8 xor eax,dword ptr [a] 0041150D 89 45 EC mov dword ptr [b],eax 25: a^=b; 00411510 8B 45 F8 mov eax,dword ptr [a] 00411513 33 45 EC xor eax,dword ptr [b] 00411516 89 45 F8 mov dword ptr [a],eax

*MSVC*

[helios]

guestgulkan: Could you try optimized?

[jsmith]

Fascinating. I've no fear:

g++ -O6 foo.cpp -S

on the following code:

#include <stdio.h>
#include <stdlib.h>

inline void swap1( int& a, int& b ) {
    a ^= b;
    b ^= a;
    a ^= b;
}

inline void swap2( int& a, int& b ) {
   int temp = a;
   a = b;
   b = temp;
}

int main() {
    int x = rand(), y = rand();
    swap1( x, y );
    printf( "%d %d", x, y );
    swap2( x, y );
    printf( "%d %d", x, y );
}

Both algorithms generated the exact same code, which is to say... none.

The compiler seems to recognize the swap algorithm because the assembler it generated was to store x in %esi and y in %ebx, and then it just pushed the two parameters onto the stack for the call to printf() in swapped order in both cases.


EDIT: now if I remove the keyword "inline" then the compiler actually generates function calls, and my results largely concur with guestgulkan's even at O6: the assembler shows 8 memory accesses in the XOR case (5 moves and 3 xors) and 6 in the temporary case (all moves).