Tuesday, September 15, 2009

Using Quicksort (Qsort) on microcontrollers

Need to sort an array of numbers? I needed to do this on a microcontroller and Quicksort did the trick, very easily. Here's how:

1. Need to include stdlib:
#include //for qsort
2. Need to make a comparison function. For 2-byte integers it's pretty easy:
int comp(const void * a, const void * b)
{
int* aa = (int*) a;
int* bb = (int*) b;
if (*aa==*bb)
return 0;
else
if (*aa < *bb)
return -1;
else
return 1;
}
3. The arguments for qsort are:
a) the array to sort
b) The number of elements to sort (starting from the element at index==0 in the array)
c) The size (in bytes) of what you are sorting
d) the comparison function you wish to use.
See the following example:
void testSort()
{
int numbers[]={1892,45,200,-98,-4,5,-123,107,88,-1000};
printf("Before sorting: ");
for (int i=0;i<9;i++)
printf(" %d ",numbers[ i ]) ;
qsort(numbers,10,sizeof(int),comp) ;
printf("\r\nAfter sorting: ");
for (int i=0;i<9;i++)
printf(" %d ",numbers[ i ]) ;
printf("\r\n");
}
For more information, see http://cplus.about.com/od/learningc/ss/pointers2_8.htm

2 comments:

  1. Alas, it appears the BlogSpot "helpfully" deleted the left-bracket, "stdlib.h", right-bracket from the "#include" line in this code.

    I'm starting to see some programmers avoid using the "less-than" symbol wherever possible, shuffling things around and replacing it with the "greater-than" symbol, precisely because of this kind of "help".

    ReplyDelete
  2. Thanks, I didn't notice it. There should be a blogspot option for code; ie. apply no formatting.

    ReplyDelete