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?

Answer 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 up to 3 comparisons, but only two swaps.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

I always like http://www.sorting-algorithms.com/, the animations help me see how the algorithms work.

Answer 7

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.