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