I assume that by
I'm also really looking for the avg Top 4 values.
you mean that you will find the largest four numbers and report their average.
If so, you can sort all the values (as in previous answer) and then average the last four numbers (or first four, depending on sort order) from the sorted array. This has complexity O(n lg n), that is, sort time grows with array size n as the product n times logarithm of n.
Or, you can keep track of the largest four values as you iterate through the array, via technique illustrated in code at the end of this answer. This has complexity O(n lg k), that is, sort time grows with array size n and number k of high values as the product n times logarithm of k.
In using qsort, I prefer (in this edit) to write the comparator function more compactly, although possibly less transparently, by using *(int*)a to reference the value that a points to. For example:
// Comparator function for integers
int compareInt (const void *a, const void *b) {
// Return -, 0, or + if first value is <, =, or > second value.
return *(int*)a - *(int*)b;
}
You can make the comparator sort descending (so that the largest four numbers appear in array's first four slots) by using return *(int*)b -*(int*)a; instead of the return that's shown.
Templated, the function looks as follows.
template<typename T>
// Comparator function for Numbers
int compareNumber (const void *a, const void *b) {
// Return -, 0, or + if first value is <, =, or > second value.
return *(T*)a -*(T*)b;
}
I called the routine compareNumber because it uses subtraction to find out which operand is larger. But as explained in arduino.cc's String Comparison Operators page, for Arduino String-type objects, subtraction is bound to string comparison, so the above templated function works with String objects as well as numbers.
For C-type strings, which are character arrays terminated by a null character, ie of char* or char[] type, the strcmp() function can be used directly as qsort()'s comparator function:
qsort(arrayOfPointersToCStrings, elementCount, pointersize, strcmp);
That is, there is no reason to write a separate comparator function with a call to strcmp(); just reference strcmp() directly.
When you have a small, fixed number of values to process, just doing a sort is reasonable. The algorithmic complexity is O(n*lg n), and if n is fixed, this is basically O(1). If, however, you were processing extremely large data sets and wanted to identify the largest four numbers without storing all the other numbers, you can track the largest four by keeping the four largest numbers so far seen in an array. This has algorithmic complexity that is O(n*k) at worst, where k is the number of elements tracked; and for fixed k, this is O(n). If k is large or variable, a tree method can be used to get complexity O(n*lg k).
Anyhow, suppose the array is int largestSoFar[4]. Initialize each entry in that array to some number smaller than any valid data item; eg, to INT_MIN from <limits.h>.
As each new data item arrives, compare it to largestSoFar[0]. If it's less or equal, go get the next data item.
Else, the new value is one of the largest values so far seen. Store it in largestSoFar[0], then have a loop to do compare-and-swap steps to ripple the new number up to its appropriate level. That is, compare elements [0] and [1]; break if largestSoFar[0]<largestSoFar[1], else swap[0] and [1] and go on to compare-and-swap for elements [1] and [2], etc.
The code below (shown as a standalone C program, rather than as an Arduino sketch) illustrates the technique. Here is what it prints out:
Linear result: 2654 2720 2815 2961 2968 9662 Total: 23780
Sorting result: 9662 2968 2961 2815 2720 2654 Total: 23780
Here is the standalone C program illustrating a linear (O(1)) method:
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
// Comparator function
int intCompare(const void *va, const void *vb) {
const int a = *(int*)va, b = *(int*)vb;
// (a>b) is 1 if a>b, else 0. (b>a) is 1 if b>a, else 0.
// So the following expression has value 1, 0, or -1.
return (b>a) - (a>b); // To sort descending
}
int main () {
int someNumbers [] = { 481, 1041, 107, 279, 809, 2052, 2961, 557,
2534, 2968, 89, 839, 2720, 85, 2115, 898,
1931, 655, 2631, 1897, 2322, 1115, 2815, 674,
2259, 176, 598, 525, 600, 1088, 1885, 313,
1175, 2654, 915, 536, 978, 2052, 798, 1979,
2571, 2154, 1138, 259, 9662 };
enum { NumTop = 6, NumNum = (sizeof someNumbers)/sizeof(int) };
int i, j, tot, largestSoFar[NumTop];
for (i = 0; i < NumTop; ++i)
largestSoFar[i] = INT_MIN; // Init. largestSoFar[] to smallest numbers
// Process all the numbers
for (j = 0; j < NumNum; ++j) {
if (someNumbers[j] <= largestSoFar[0])
continue;
// Install number into largestSoFar[] and bubble it up
largestSoFar[0] = someNumbers[j];
for (i = 1; i < NumTop; ++i) {
if (largestSoFar[i] < largestSoFar[i-1]) {
int t = largestSoFar[i];
largestSoFar[i] = largestSoFar[i-1];
largestSoFar[i-1] = t;
}
else break;
}
}
printf ("Linear result: ");
for (i = tot = 0; i < NumTop; ++i) {
printf ("%5d ", largestSoFar[i]);
tot += largestSoFar[i];
}
printf (" Total: %d\n", tot);
// sort the array descending, for comparison
qsort (someNumbers, NumNum, sizeof(int), intCompare);
printf ("Sorting result: ");
for (i = tot = 0; i < NumTop; ++i) {
printf ("%5d ", someNumbers[i]);
tot += someNumbers[i];
}
printf (" Total: %d\n", tot);
return 0;
}
