Hello all,
I have some data that I would like to sort on a micro controller. Is there a very good way for doing that. I can't use the qsort() in the stdlib.h because it is not available on my platform.
Are there any suggestions on what kind of sorting to use.
Regards,
M.T
How much data? What type of data? Where does it come from? Where is it going? What else is the Arduino doing?
I have the choice to select how much data. The data is a stream of time series data from a data logger. I process the time series data and get the mean at different time intervals.
My algorithm then dictates me to sort these in order to recognize the patterns that I am looking for. The data are 32bit floating point, (4 bytes) and right now, i am working with a fixed set of 100 data points. This will change, so I need to use an efficient sort..
Regards,
MT
Just write one sort function in your PC, using floats and 100 distinct data samples means 400Bytes of ram, thats inside the arduino capabilities, but sorting arrays fast is not.
What environment are you using that you cannot create one sort function?!
I am using Codevision AVR on atmega 2560.. I usually use Arduino but I am forced to use this for now..
I know that sorting can be made faster with a binary tree or other fancy data structure, but I do not want to get that detailed in this project, i just want to sort the damn thing.. I tried going through the array comparing 2 elements at a time and swapping them but that was terribly inefficient..
This is a C implementation of the quicksort algorithm (from here: QUICKSORT (Java, C++) | Algorithms and Data Structures):
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
Your biggest issue with using this on the Arduino might be stack limitations for the recursion, but I think it might be worth a shot to try.
If you were using a simple Bubble Sort (which is what you might be describing), you might want to look into better variants of it which might work better for your data:
I have had pretty good luck on small arrays (like your example) with some of the variants of the Bubble Sort (and there are many). The nice thing about many of these is that they don't rely on recursion (so you don't have to worry about stack space issues - which is generally only an issue on a microcontroller).
Read up on some of the simpler sorting algorithms, and try them out (be sure to try out the quicksort, too) - try to see where their limits are, then pick the one that works best for your needs.
Good luck.
Just because you're using a different C library doesn't mean you can't borrow some goodies from AVR-LIBC:
The qsort function there looks pretty self-contained and should only require minor edits to get rid of the AVR-LIBC-specific macros.
It also looks fairly well thought out for a microcontroller implementation.
--
The Rugged Motor Driver: two H-bridges, more power than an L298, fully protected
Do you need sorting?
Can the system not be made different?
e.g. the application that writes the dataseries could write it in another order?
You could also process the part of the array that is sorted. Instead of first sorting and then processing you could do :