The Fastest way to sort 3 values

March 8, 2010 by Luigi Giaccari · Leave a Comment
Filed under: C, Optimization

Rating: 0 (from 0 votes)

Rating: 0.0/10 (0 votes cast)

Yesterday I was surfing the web looking for some optimized C++ code to sort 3 numbers. Here is an excerpt from the first page returned by Google.

The problem of sorting 3 numbers can be described as follow

a < b	a < c	b < c	a < b < c here, sorted!!!
			a < c <= b here, sorted
		c <= a < b here, sorted!!!
	b < c	a < c	b <= a < c here, sorted!!!
			b < c <= a here, sorted!!!
		c <= b <= a here, sorted!!!

A binary tree is used to reach the solution.

This leads to the following code:

! -------------------------------------------------------
 ! This program reads in three INTEGERs and displays them
 ! in ascending order.
 ! -------------------------------------------------------

 PROGRAM Order
 IMPLICIT NONE

 INTEGER :: a, b, c

 READ(*,*)  a, b, c

 IF (a < b) THEN ! a < b here
 IF (a < c) THEN !   a < c     : a the smallest
 IF (b < c) THEN !      b < c  : a < b < c
 WRITE(*,*)  a, b, c
 ELSE !      c <= b : a < c <= b
 WRITE(*,*)  a, c, b
 END IF
 ELSE !   a >= c    : c <= a < b
 WRITE(*,*) c, a, b
 END IF
 ELSE ! b <= a here
 IF (b < c) THEN !   b < c     : b the smallest
 IF (a < c) THEN !     a < c   : b <= a < c
 WRITE(*,*)  b, a, c
 ELSE !     a >= c  : b < c <= a
 WRITE(*,*)  b, c, a
 END IF
 ELSE !   c <= b    : c <= b <= a
 WRITE(*,*)  c, b, a
 END IF
 END IF

 END PROGRAM Order

Another guy suggested that this solution is too complicated and proposed:

int a, b, c;
 
 #define swap(x, y) do {int tmp; tmp = x; x = y; y = tmp; } while (0)
 
 if (b < a) swap(b, a);
 if (c < b) swap(c, b);
 if (b < a) swap(b, a);

This can also be easly extended to 4 numbers :

if (b < a) swap(b, a);
 if (c < b) swap(c, b);
 if (d < c) swap(d, c);
 if (b < a) swap(b, a);
 if (c < b) swap(c, b);
 if (b < a) swap(b, a);

This program is nothing less than bubble sort. It can be generated with the following program:

main()
 
for (i = 0; i < n - 1; i++)
 for (j = 0; j < n - 1 - i; j++)
 printf("if (%c < %c) swap(%c, %c);\n",
 'a' + j + 1, 'a' + j, 'a' + j + 1, 'a' + j);
 }

This code may be easier to write but it is slower, I have compared the easy solution (with swaps form bubble sort) with the more complicated one that uses a binary tree.

Sorting 10′000′000 3 numbers buckets took 187ms with the bubble sort, 158mswith binary tree. I coded a in place version of a 3 numbers sort function.

Here is the fastest code I know to sort in place 3 numbers:

void sort3(double* a){
double temp;
if (a[0]<a[1]){
if (a[1]<a[2]){
//012
}
else{
if (a[0]<a[2]){
//021
temp=a[1];
a[1]=a[2];
a[2]=temp;
}
else{
//201
temp=a[0];
a[0]=a[2];
a[2]=temp;
temp=a[1];
a[1]=a[2];
a[2]=temp;
}
}
}
else{
if (a[0]<a[2]){
//102
temp=a[0];
a[0]=a[1];
a[1]=temp;
}
else{
if (a[1]<a[2]){
//120
temp=a[0];
a[0]=a[1];
a[1]=a[2];
a[2]=temp;
}
else{
//210
temp=a[0];
a[0]=a[2];
a[2]=temp;
}
}
}
}

Notice that there is no swap macros. Swaps are optimized avoiding to copy the temp value when is not necessary. So now I have to propose you some interesting challenge.