# Tutorial :How to sort three variables using at most two swaps? ### Question:

The following algorithm can sort three variables `x`, `y` and `z` of type `K` which are comparable using `operator<`:

``void sort2(K& x, K& y) {     if(y < x)        swap(x, y);  }          void sort3(K& x, K& y, K& z) {     sort2(x, y);     sort2(y, z);     sort2(x, y);  }  ``

This needs three swaps in the "worst case". However basic mathematics tells us, that the ordering of three values can be done using only two swaps.

Example: The values (c,b,a) will be sorted using three swaps: (c,b,a) -> (b,c,a) -> (b,a,c) -> (a,b,c). However one swap would have been enough: (c,b,a) -> (a,b,c).

What would be the simplest algorithms which sorts three variables with at most two swaps in all cases?

### Solution:1

Find the smallest, this takes 2 comparisons, and swap it into the first position. Then compare the remaining 2 and swap if necessary.

``if (x < y) {     if (z < x) swap(x,z);  } else {    if (y < z) swap(x,y);    else swap(x,z);  }   if(z<y) swap(y,z);  ``

This takes 3 comparisons, but only two swaps.

### Solution:2

``void sort(int& a, int& b, int& c)  {     swap(a, min(a, min(b, c)));     swap(b, min(b, c));  }  ``

2 swaps, 3 comparisons.

### 2 to 3 comparisons, 0 to ~1.7 swaps

Old question, new answer... The following algorithm sorts `x`, `y` and `z` with 2 to 3 comparisons depending on their values and 0 to ~1.7 swap operations.

``void sort3(K& x, K& y, K& z)  {          if (y < x) {          if (z < x) {              if (z < y) {                  swap(x, z);              } else {                  K tmp = std::move(x);                  x = std::move(y);                  y = std::move(z);                  z = std::move(tmp);              }          } else {              swap(x, y);          }      } else {          if (z < y) {              if (z < x) {                  K tmp = std::move(z);                  z = std::move(y);                  y = std::move(x);                  x = std::move(tmp);              } else {                  swap(y, z);              }          }      }  }  ``

So, how does it work? It's basiccaly an unrolled insertion sort: if the values are already sorted (it takes 2 comparisons to check that) then the algorithm does not swap anything. Otherwise, it performs 1 or 2 swap operations. However, when 2 swap operations are required, the algorithm Â«Â rotatesÂ Â» the values instead so that 4 moves are performed instead of 6 (a swap operation should cost 3 moves, unless optimized).

There are only 6 possible permutations of 3 values. This algorithm does the comparisons needed to know which permutation we're treating. Then it does the swapping and leaves. Therefore, the algorithm has 6 possible paths (including the one where it does nothing because the array is already sorted). While it's still human-readable, an equivalently optimal algorithm to sort 4 values would have 24 different paths and would be much harder to read (for n values, there are n! possible permutations).

Since we're already in 2015 and you seemed to be using C++, I took the liberty use `std::move` so to make sure that the swap-rotate thingy would be efficient enough and would work even for moveable but non-copyable types.

### Solution:4

Find the minimum value and swap it with the first value. Find the second minimum and swap it with the second value. Two swaps at most.

This is basically selection sort, which will perform at most `n - 1` swaps.

### Solution:5

If you don't do it in place, you can perform it without any swaps.

### Solution:6

Encode a sorting network in a table. The Wikipedia article I linked should help you with references in case you need to figure out what to put in the table in other cases (i.e., bigger arrays).

### Solution:7

I think what you want is to find the optimal swap in each step instead of just a valid swap. To do that, just find the greatest difference between an element and an element later in the list and swap those. In a 3-tuple, there are three possible swaps, 1-3, 1-2, and 2-3. At each step find the max difference among these three swaps and do that. Pretty sure that gives two swaps in the worst case for 3 elements. Only really makes sense if swapping is relatively expensive compared to comparing elements, otherwise probably not worth the additional analysis upfront.

### Solution:8

Cool question :)

If assembly is available to you, and the values fit in a register, then you can probably do it extremely fast by just loading them into registers and doing a few compares, jumping to the right scenario to put the values back. Maybe your compiler makes this optimization already.

Either way, if performance is your goal, take a look at the generated machine code and optimize there. For such a small algorithm that's where you can squeeze performance out of.

### Solution:9

I recently had to solve a similar problem - sort three values efficiently. You concentrate on swap-operations in your question. If performance is what you are looking for, concentrate on the comparison operations and branches! When sorting such a "tiny" array with just three values, a good idea is to consider using additional storage, which is appropriate for so few values. I came up with something like a specialized "merge sort" (see code below).

Just as tenfour suggests, I looked at the assembly, and the code below compiles down to a compact inline set of CPU-register operations, and is extremely fast. The additional variable "arr12" is also stored in the CPU-registers. The sorting requires two or three comparison operations. The function can easily be converted to a template (not given here for clarity).

``inline void sort3_descending( double * arr )  {      double  arr12[ 2 ];        // sort first two values      if( arr[ 0 ] > arr[ 1 ] )      {          arr12[ 0 ] = arr[ 0 ];          arr12[ 1 ] = arr[ 1 ];      } // if      else      {          arr12[ 0 ] = arr[ 1 ];          arr12[ 1 ] = arr[ 0 ];      } // else        // decide where to put arr12 and the third original value arr[ 3 ]      if( arr12[ 1 ] > arr[ 2 ] )      {          arr[ 0 ] = arr12[ 0 ];          arr[ 1 ] = arr12[ 1 ];      } // if      else if( arr[ 2 ] > arr12[ 0 ] )      {          arr[ 0 ] = arr  [ 2 ];          arr[ 1 ] = arr12[ 0 ];          arr[ 2 ] = arr12[ 1 ];      } // if      else      {          arr[ 0 ] = arr12[ 0 ];          arr[ 1 ] = arr  [ 2 ];          arr[ 2 ] = arr12[ 1 ];      } // else  }  ``

### Solution:10

This can illustrated with a truth table relating to every possible combination of comparisons to see how we can best optimize the swap you mention here.

Values | x < y | y < z | x < z

x,y,z | y | y | y

x,z,y | y | n | y

y,x,z | n | y | y

y,z,x | n | y | n

z,x,y | y | n | n

z,y,x | n | n | n

By framing the question this way, we can easily see that by initially checking and swapping the 1st and 3rd element, the lowest value that we can have in the first element after the swap can either be x or y. This simplifies the if check afterwards so that we can either swap the 1st and 2nd element when x > y or swap the 2nd and 3rd element when y > z.

``if (x > z) {      swap(x,z);  }    if (x > y) {      swap(x,y);  } else if (y > z) {      swap(y,z);  }  ``

No need for any nested if conditionals. Just 2-3 simple comparisons for 2 swaps at max.

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »