Triangle swap

As Triangle exchange is known in programming a method for replacing the values of two variables . An auxiliary variable is used to temporarily store the value of the variable that is overwritten first. A typical application of the triangle swap consists, for example, in some sorting algorithms such as the bubble sort .

functionality

The general principle is as follows:

{\ displaystyle t: = v_ {1}}

{\ displaystyle v_ {1}: = v_ {2}}

{\ displaystyle v_ {2}: = t}

Here is the temporary auxiliary variable, usually referred to as in program code , and and are the variables to be swapped. ${\ displaystyle t}$ temp ${\ displaystyle v_ {1}}$ ${\ displaystyle v_ {2}}$

Triangular exchange of numerical values

Two other options for swapping ordinals without auxiliary variables are repeated adding and subtracting:

{\ displaystyle v_ {1}: = v_ {1} + v_ {2}}

{\ displaystyle v_ {2}: = v_ {1} -v_ {2}}

{\ displaystyle v_ {1}: = v_ {1} -v_ {2}}

or:

{\ displaystyle v_ {1}: = v_ {1} -v_ {2}}

{\ displaystyle v_ {2}: = v_ {1} + v_ {2}}

{\ displaystyle v_ {1}: = v_ {2} -v_ {1}}

This method should not be used with floating point numbers as it can lead to deletions . Strictly speaking, it is no longer a triangle swap.

The following also works for numerical values:

{\ displaystyle v_ {1}: = v_ {2} +0 \ cdot (v_ {2}: = v_ {1})}

Triangle exchange with binary values

If the values of the two variables to be exchanged are binary-linked values, the exchange can also be implemented entirely without auxiliary variables by means of repeated XOR operations , based on the law . ${\ displaystyle (a \, {\ underline {\ lor}} \, b) \, {\ underline {\ lor}} \, b = a}$

{\ displaystyle v_ {1}: = v_ {1} \, {\ underline {\ lor}} \, v_ {2}}

{\ displaystyle v_ {2}: = v_ {1} \, {\ underline {\ lor}} \, v_ {2}}

{\ displaystyle v_ {1}: = v_ {1} \, {\ underline {\ lor}} \, v_ {2}}

To do this, the two variables must be in different places in the memory. If this is not the case, this triangle swap resets the value of the variable to 0.

In some programming languages, including C ++ and C #, the instruction works on data types that support the binary XOR link

v1 ^= v2 ^= v1 ^= v2;

Here the expression stands a ^= bfor . ${\ displaystyle a: = a \, {\ underline {\ lor}} \, b}$

Multiple assignments

Some programming languages, such as Ruby , Python , F # and Powershell , also support multiple assignments with the help of tuples , which makes triangle swapping unnecessary:

{\ displaystyle (v_ {1}, v_ {2}): = (v_ {2}, v_ {1})}

Modern processors also have their own commands for swapping variables, including xchgand cmpxchg.

Program examples

Assembler

# x86, x64, ARM
xchg v1, v2

C #

void Swap<T>(ref T v1, ref T v2)
{
    var temp = v1;
    v1 = v2;
    v2 = temp;
}

void Swap<T>(ref T v1, ref T v2)
{
    // preferred method 
    // compiles to single instruction
    v2 = Interlocked.Exchange(ref v1, v2); 
}

Tuple<T, T> Swap<T>(Tuple<T, T> tuple)
{
    return new Tuple(tuple.Item1, tuple.Item2);
}

F #

let swap (v1, v2) = (v2, v1)

Powershell

$v1,$v2 = $v2,$v1

JavaScript

var temp = feld[i];
feld[i] = feld[i+1];
feld[i+1] = temp;

python

x, y = y, x