Sunday, June 26, 2011

Simple Algorithms - Swapping Values

We have three integer variables a,b,c. What are the steps to be followed to move value of a to b, b to c and c to a without using any extra variable?

To solve this we will try to find out a sub-problem first. This will make the task easier. A very simple problem is to swap values of two integer variables without using a third variable. Let a and b are two variables. The solution is:

swap(a,b) {
a=a+b;
b=a-b;
a=a-b;
}

The proof:

a =a+b; ----(1)
b=a-b=A(a+b) using (1) -b= a;---(2)
a=a-b= A(a+b) using (1)-B(a) using (2)=b;

Note: A(a+b) represents current value in variable a and so on.


Now if we have three variables a,b,c to move value of a to b, b to c and c to a we can follow following steps:

swap(a,b);
swap(a ,c);


So, what could be the algorithm if we have four integer variables i.e a, b, c, d ?

No comments:

Post a Comment