# Do I need a bubble sort or something easier?

I'm using an Arduino Leonardo and a GPSTiny++ library to parse NMEA strings from my GPS receiver. In this chunk of code I'm averaging all satellite SNR numbers for satellites which are locked (Being used for navigation). The avg value provides some general information on overall performance but I'm also really looking for the avg Top 4 values.

I believe I would need to do some sort of sorting algorithm. Increment through the top 4 and average those values.

Here's a snippet of my output window: 12/13 0.92 SNR=17 10 27 27 30 29 25 27 33 0 0 0 31 25.60 0.00

The second to last number is the average.

How do I get started?

``````int totalSNR = 0;
float avgSNR = 0;
int count = 0;
Serial.print(F(" SNR="));
for (int i = 0; i < MAX_SATELLITES; ++i)
if (sats[i].active)
{
if (sats[i].snr > 0) {
count++;
totalSNR = totalSNR + sats[i].snr;
}

Serial.print(sats[i].snr);
Serial.print(F(" "));
}

avgSNR = float(totalSNR) / float(count);
Serial.print(avgSNR);
``````

You could do a qsort. You haven't posted any data types so it is hard to answer with your specific code, however here is a sample of sorting numbers:

``````const int COUNT = 10;

int someNumbers [COUNT] = { 7342, 54, 21, 42, 18, -5, 30, 998, 999, 3  };

// callback function for doing comparisons
int myCompareFunction (const void * arg1, const void * arg2)
{
int * a = (int *) arg1;  // cast to pointers to integers
int * b = (int *) arg2;

// a less than b?
if (*a < *b)
return -1;

// a greater than b?
if (*a > *b)
return 1;

// must be equal
return 0;
}  // end of myCompareFunction

void setup ()
{
Serial.begin (115200);
while (!Serial) { }  // for Leonardo
Serial.println ();
// sort using custom compare function
qsort (someNumbers, COUNT, sizeof (int), myCompareFunction);
for (int i = 0; i < COUNT; i++)
}  // end of setup

void loop () { }
``````

Output:

``````-5
3
18
21
30
42
54
998
999
7342
``````

## Generic compare function with a template

Interestingly, you can make the compare function be a template which lets you compare any type -- that is, any type that supports direct comparisons. Change the compare function to:

``````// callback function for doing comparisons
template<typename T>
int myCompareFunction (const void * arg1, const void * arg2)
{
T * a = (T *) arg1;  // cast to pointers to type T
T * b = (T *) arg2;
// a less than b?
if (*a < *b)
return -1;
// a greater than b?
if (*a > *b)
return 1;
// must be equal
return 0;
}  // end of myCompareFunction
``````

This change removes the reference to "a" and "b" being "int" and replaces them with T, which is the template type.

Now we can change the qsort line to be:

``````  // sort using custom compare function
qsort (someNumbers, COUNT, sizeof (int), myCompareFunction<int>);
``````

That gives the same results, but now we can also compare float, long, unsigned long, byte, all that sort of thing.

## Compare floats

For example to compare floats:

``````const int COUNT = 10;

float someNumbers [COUNT] = { 7342, 54, 21, 42, 18, -5, 30, 998, 999, 3  };

// callback function for doing comparisons
template<typename T>
int myCompareFunction (const void * arg1, const void * arg2)
{
T * a = (T *) arg1;  // cast to pointers to type T
T * b = (T *) arg2;
// a less than b?
if (*a < *b)
return -1;
// a greater than b?
if (*a > *b)
return 1;
// must be equal
return 0;
}  // end of myCompareFunction

void setup ()
{
Serial.begin (115200);
while (!Serial) { }  // for Leonardo
Serial.println ();
// sort using custom compare function
qsort (someNumbers, COUNT, sizeof (float), myCompareFunction<float>);
for (int i = 0; i < COUNT; i++)
}  // end of setup

void loop () { }
``````

The only change there was changing the word "int" to "float" (in two places) on the qsort line, and on the data declaration itself.

## Compare String objects

You can even compare String objects (not C strings), for example the data is:

``````String someStrings [COUNT] = { "the", "quick", "brown", "fox", "jumped",
"over", "the", "lazy", "dog", "ZOMG"  };
``````

And the sort is:

``````  // sort using custom compare function
qsort (someStrings, COUNT, sizeof (String), myCompareFunction<String>);
for (int i = 0; i < COUNT; i++)
Serial.println (someStrings [i]);
``````

## Compare C strings

We need to use `strcmp` in this case, but most of the work is done in that. We just have to dereference the pointer so `strcmp` gets the pointer to the string (not the pointer to the pointer to the string).

``````char * someStrings [COUNT] = { "the", "quick", "brown", "fox", "jumped",
"over", "the", "lazy", "dog", "ZOMG"  };

int myCompareFunction (const void * arg1, const void * arg2)
{
return strcmp (*(char **) arg1, *(char **) arg2);
}  // end of myCompareFunction

void setup ()
{
Serial.begin (115200);
while (!Serial) { }  // for Leonardo
Serial.println ();
// sort using custom compare function
qsort (someStrings, COUNT, sizeof (char *), myCompareFunction);
for (int i = 0; i < COUNT; i++)
Serial.println (someStrings [i]);
}  // end of setup

void loop () { }
``````

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`. 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`. 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`, then have a loop to do compare-and-swap steps to ripple the new number up to its appropriate level. That is, compare elements  and ; break if `largestSoFar<largestSoFar`, else swap and  and go on to compare-and-swap for elements  and , 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) {
continue;
// Install number into largestSoFar[] and bubble it up
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
printf ("Sorting result: ");
for (i = tot = 0; i < NumTop; ++i) {
}
printf ("   Total: %d\n", tot);
return 0;
}
``````
• Nice answer. I like the way you address the complexity of the various methods. :) The linear approach will be faster, although at the cost of RAM. If the OP wanted to average more numbers (eg. the top 100) then RAM might start to become an issue. Jul 10 '15 at 1:31

Since you only need to know the 4 largest values in the array you don't need to sort the array, you just need to iterate through it and find the four largest values. This can be done in `O(n*k)` which is faster than any sorting algorithm you could use. However there is an issue of space since you would use an array to hold the previous largest numbers. Fortunately we can get around this by swapping the current largest value to the end of the array and ignoring it. So you can find the `k` largest values in an size `n` array in `O(n*k)` time complexity with `O(1)` space complexity. For fixed values if `n` and `k` the time complexity is `O(1)`.

`````` #include <stdio.h>

void swap (int& a, int& b);

int main () {

int sum = 0;
int max = -1; // I'm assuming your array will have non-negative numbers
int maxIndex;
int nums = 4; // we want the top "num" values in the array

const int arrSize = 9;
int arr[arrSize] = {36, 33, 19, 42, 47, 26, 50, 37, 38}; // random numbers

for (int i = 0; i < num; ++i){
// arrSize - i lets us ignore the previous max values
for (int j = 0; j < arrSize - i; j++){
if(arr[j] > max){
max = arr[j]; // store current max
maxIndex = j; // store the current max's index
}
}
sum += max; // running total
max = -1;   // reset max
swap(arr[maxIndex], arr[arrSize-1-i]); // move current max to the end
}

float top4Avg = sum / 4.0;
printf("\nTop 4 average: %f\n", top4Avg);

}

// swaps a and b without a temp variable
void swap (int& a, int& b){
a = a ^ b; // ^ is the bitwise xor
b = a ^ b;
a = a ^ b;
}
``````

First iteration: `{36, 33, 19, 42, 47, 26, 38, 37, 50}`

Second iteration: `{36, 33, 19, 42, 37, 26, 38, 47, 50}`

Third iteration: `{36, 33, 19, 38, 37, 26, 42, 47, 50}`

Fourth iteration: `{36, 33, 19, 26, 37, 38, 42, 47, 50}`

Also this was a really fun question I'd upvote but my rep isn't high enough.

• Comment “// arrSize - 1 lets us ignore the previous max values” should instead refer to `arrSize - i` May 11 '17 at 14:16