The Fastest way to sort 3 values
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.
Can this be called the “QuickestSort algorithm” ?
Can you find or code something faster? Let me know.
And can you figure out what is the fastest way to sort 4 numbers?
keep in touch with blog and you will see how.
Popularity: 1% [?]
Related Posts
Comments
Tell me what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!
Include MATLAB code in your comment by doing the following:
<pre lang="MATLAB">
%insert code here
</pre>
Translator
Follow Us
Video Posts
