Sorting multidimensional arrays according to multiple criteria

Projects Programming
1

I don't think my issue is necessarily Arduino related, probably just poor C code, but it is code running on an Arduino. I'm trying to sort an array that's storing DS18B20 temperature readings. I use the DS18B20's high/low alarm set points to store each sensor's bin and sensor ID number. The Arduino is reading multiple bins and if you've worked with these 1-wire sensors before, you know that they are read in a random order. I have a 2d byte array storing their bin ID, sensor ID and temperature reading and for display purposes, I'd like to sort them in order of bin ID, then sensor ID using as little RAM as possible. Here's what I've got. TempSensorReadings is declared globally.

int TempSensorReadings[100][3];

void SortTempSensors(){
  
  Serial.print(F("\r\nUnsorted list:"));
  PrintSensorList();

  byte temp[3];
  //first sort by least important criteria, in this case sensor ID number
  for (byte i=0;i<NumTempSensors-1;i++){
    for (byte t=i+1;t<NumTempSensors;t++){
      if (TempSensorReadings[t][1]<TempSensorReadings[i][1]){
        temp[0]=TempSensorReadings[t][0];
        temp[1]=TempSensorReadings[t][1];
        temp[2]=TempSensorReadings[t][2];
        TempSensorReadings[t][0]=TempSensorReadings[i][0];
        TempSensorReadings[t][1]=TempSensorReadings[i][1];
        TempSensorReadings[t][2]=TempSensorReadings[i][2];
        TempSensorReadings[i][0]=temp[0];
        TempSensorReadings[i][1]=temp[1];
        TempSensorReadings[i][2]=temp[2];
      }
    }
  }
  Serial.print(F("\r\nHalf sorted list:"));
  PrintSensorList();

  //then sort by most important criteria, in this case bin ID number
  for (byte i=0;i<NumTempSensors-1;i++){
    for (byte t=i+1;t<NumTempSensors;t++){
      if (TempSensorReadings[t][0]<TempSensorReadings[i][0]){
        temp[0]=TempSensorReadings[t][0];
        temp[1]=TempSensorReadings[t][1];
        temp[2]=TempSensorReadings[t][2];
        TempSensorReadings[t][0]=TempSensorReadings[i][0];
        TempSensorReadings[t][1]=TempSensorReadings[i][1];
        TempSensorReadings[t][2]=TempSensorReadings[i][2];
        TempSensorReadings[i][0]=temp[0];
        TempSensorReadings[i][1]=temp[1];
        TempSensorReadings[i][2]=temp[2];
      }
    }
  }
  Serial.print(F("\r\nSorted list:"));
  PrintSensorList();
}

void PrintSensorList(){
   for (byte i=0;i<NumTempSensors;i++){
    Serial.print(F("\r\nSensor "));
    Serial.print(TempSensorReadings[i][0]);
    Serial.print(F(" : "));
    Serial.print(TempSensorReadings[i][1]);
    Serial.print(F(" = "));
    Serial.print(TempSensorReadings[i][2],DEC);
  }
}

There are some strange, random happenings...usually just one or two sensors' temperature is corrupted, sometimes a few. One common theme I've observed is the second last sensor in the list often see's it's data corrupted, almost always during the second sort and often during the first sort too. Sorry for the long post, I'm not sure how else to explain my problem. Hopefully my entire post does not get quoted. I'm sure there's better ways of doing this.

Unsorted list:
Sensor 1 : 2 = 236
Sensor 1 : 3 = 240
Sensor 1 : 4 = 236
Sensor 1 : 5 = 236
Sensor 1 : 1 = 236
Sensor 1 : 6 = 261
Sensor 33 : 4 = 253
Sensor 33 : 6 = 253
Sensor 9 : 2 = 263
Sensor 9 : 1 = 265
Sensor 10 : 2 = 252
Sensor 9 : 3 = 260
Sensor 10 : 1 = 252
Sensor 10 : 3 = 231
Half sorted list:
Sensor 1 : 1 = 236
Sensor 9 : 1 = 9
Sensor 10 : 1 = 252
Sensor 1 : 2 = 236
Sensor 10 : 2 = 252
Sensor 9 : 2 = 7
Sensor 9 : 3 = 4
Sensor 1 : 3 = 240
Sensor 10 : 3 = 231
Sensor 1 : 4 = 236
Sensor 33 : 4 = 253
Sensor 1 : 5 = 236
Sensor 1 : 6 = 261
Sensor 33 : 6 = 253
Sorted list:
Sensor 1 : 1 = 236
Sensor 1 : 2 = 236
Sensor 1 : 3 = 240
Sensor 1 : 4 = 236
Sensor 1 : 5 = 236
Sensor 1 : 6 = 5
Sensor 9 : 2 = 7
Sensor 9 : 3 = 4
Sensor 9 : 1 = 9
Sensor 10 : 2 = 252
Sensor 10 : 1 = 252
Sensor 10 : 3 = 231
Sensor 33 : 4 = 253
Sensor 33 : 6 = 253

Sensor 1 : 2 = 236
Sensor 1 : 3 = 240
Sensor 1 : 4 = 236
Sensor 1 : 5 = 236
Sensor 1 : 1 = 236
Sensor 1 : 6 = 261
Sensor 33 : 4 = 252
Sensor 33 : 6 = 250
Sensor 9 : 2 = 251
Sensor 9 : 1 = 253
Sensor 10 : 2 = 251
Sensor 9 : 3 = 249
Sensor 10 : 1 = 251
Sensor 10 : 3 = 229
Half sorted list:
Sensor 1 : 1 = 236
Sensor 9 : 1 = 253
Sensor 10 : 1 = 251
Sensor 1 : 2 = 236
Sensor 10 : 2 = 251
Sensor 9 : 2 = 251
Sensor 9 : 3 = 249
Sensor 1 : 3 = 240
Sensor 10 : 3 = 229
Sensor 1 : 4 = 236
Sensor 33 : 4 = 252
Sensor 1 : 5 = 236
Sensor 1 : 6 = 261
Sensor 33 : 6 = 250
Sorted list:
Sensor 1 : 1 = 236
Sensor 1 : 2 = 236
Sensor 1 : 3 = 240
Sensor 1 : 4 = 236
Sensor 1 : 5 = 236
Sensor 1 : 6 = 5
Sensor 9 : 2 = 251
Sensor 9 : 3 = 249
Sensor 9 : 1 = 253
Sensor 10 : 2 = 251
Sensor 10 : 1 = 251
Sensor 10 : 3 = 229
Sensor 33 : 4 = 252
Sensor 33 : 6 = 250
2

A few comments to get out of the way first:

  • Please name your functions after what they are actually doing, and stick to that. In your example, "Sort..." not only sorts, it also prints the list. Keep them separate.

  • Usually constants are UPPER_CASE like that, functions start with verbs and start lowerCase(). Types start with a CapitalLetter and variables also lowerCase or lower_case - your preference.

  • If you have constants (like NumTempSensors), use them everywhere, including the array definition.

  • Mind your indentation....

  • A lot of new coders think very procedurally. Like you did there with the 2 sorting steps in a row. When you duplicate code like that - especially such large amounts, ask yourself whether that is really necessary (in this case it's definitely not). If it is, make a function instead and call it twice.

With that out of the way, lets get to the problem at hand:

The biggest glaring problem I can see is that you're using a ton of memory. 100 x 3 x int (2 bytes min) = 600 bytes just to hold all the reading. Then extra memory for libraries, sorting, serial port etc. I wouldn't be surprised if that's where some of your problems are coming from.

I would suggest (see program below) to switch to byte/byte/int at least. And if you don't need temps over 255, I'd even use byte for that.

Now regarding the sorting itself:

You can do it in one shot, if you combine the sensor ID and bin IDs. In my example I simply shift one over by a byte, but you can also simply add 1000 or so to one of them. By combining the two, you only have to sort the whole list once.

So, here's how I would approach it:

//
// Class to hold a temperature reading
//
class TempReading
{
public:
    // Data
    byte sensor;
    byte bin;
    int temp;

    //
    // Comparison operator for two TempReading
    // objects.
    //
    // Sort priority 1 = sensor ID
    // Sort priority 2 = bin ID
    //
    bool operator> (const TempReading &rhs)
    {
        return ((sensor << 8) + bin) > ((rhs.sensor << 8) + rhs.bin);
    }
};

//
// Constants
//

#define NUM_SENSORS 100

//
// Global variables
//

TempReading tempReadings[NUM_SENSORS];

//
// Print the temperature readings to the
// serial port.
//
void printSensorList()
{
    for (byte i=0; i != NUM_SENSORS; ++i)
    {
        Serial.print(F("Sensor "));
        Serial.print(tempReadings[i].sensor);
        Serial.print(F(" : "));
        Serial.print(tempReadings[i].bin);
        Serial.print(F(" = "));
        Serial.println(tempReadings[i].temp);
    }
}

//
// Sort the temperature readings.
//
// The "greater then" comparison operator in
// the TempReading class will determine the
// sort order.
//
void sortTempSensors()
{
    bool swapped;
    TempReading temp;

    do
    {
        swapped = false;
        for (byte i = 0; i != NUM_SENSORS - 1; ++i)
        {
            if (tempReadings[i] > tempReadings[i+1])
            {
                temp = tempReadings[i];
                tempReadings[i] = tempReadings[i + 1];
                tempReadings[i + 1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
}

//
// Test sorting
//
void testSort()
{
    Serial.println("Unsorted list:");
    printSensorList();

    sortTempSensors();

    Serial.println("Sorted list:");
    printSensorList();
}
3

Thanks for taking the time to read over my post and code.

int2str:

  • Please name your functions after what they are actually doing, and stick to that. In your example, "Sort..." not only sorts, it also prints the list. Keep them separate.

Sort only prints to debug it, and my print function is separate???

int2str:

  • If you have constants (like NumTempSensors), use them everywhere, including the array definition.

The number of temperature sensors is not constant.

int2str:

  • Mind your indentation....

What's wrong with my indentation? So one for..next statement is 3 spaces in, the rest are all properly indented. It looks quite obvious I try to maintain proper indentation.

int2str:

  • A lot of new coders think very procedurally. Like you did there with the 2 sorting steps in a row. When you duplicate code like that - especially such large amounts, ask yourself whether that is really necessary (in this case it's definitely not). If it is, make a function instead and call it twice.

I've been coding for years, little formal training though but what's wrong with figuring it out with some extra code. I prefer to make it work first, then condense it. Now, at first I was thinking I needed to sort it by bin ID (1st priority) then sensor ID (2nd priority) but I thought doing it in reverse was already clever. :slight_smile:

int2str:
The biggest glaring problem I can see is that you're using a ton of memory. 100 x 3 x int (2 bytes min) = 600 bytes just to hold all the reading. Then extra memory for libraries, sorting, serial port etc. I wouldn't be surprised if that's where some of your problems are coming from.

I would suggest (see program below) to switch to byte/byte/int at least. And if you don't need temps over 255, I'd even use byte for that.

I do need an int for the temperature to maintain 1/10 degree resolution, though for my current application I could probably just go with a byte and drop the decimal but for future re-purposing of this code I'd like to stay with 1/10 degree res. It could be a RAM issue though I am trying to monitor my RAM usage throughout the program and the lowest I see is 693 bytes free in a different part of the program. I don't see how my sorting code is using that much RAM.

int2str:
Now regarding the sorting itself:
You can do it in one shot, if you combine the sensor ID and bin IDs. In my example I simply shift one over by a byte, but you can also simply add 1000 or so to one of them. By combining the two, you only have to sort the whole list once.

I like the idea of combining the bin & sensor IDs. The class structure is also interesting. I'm not familiar with using them so that will require further study, especially how to adapt the rest of my code to conform.

One part I'm not yet clear on what is happening:

int2str:
//
// Comparison operator for two TempReading
// objects.
//
// Sort priority 1 = sensor ID
// Sort priority 2 = bin ID
//
bool operator> (const TempReading &rhs)
{
return ((sensor << 8) + bin) > ((rhs.sensor << 8) + rhs.bin);
}

I will try it out and study what is happening.

Interesting use of the bool swapped, clever.

So thanks for your help. The nitpicking is not appreciated and discourages inexperienced programmers from asking for help.
The helpful suggestions are very much appreciated! I will have learnt something new today.

4

I agree with the philosophy that you should make it work first, and then optimize later. But, condensing code into loops and functions can actually make it easier to debug; for example, by taking two similar blocks of code and making it into one function, you've halved the number of places bugs can hide (and once you do find a bug, halved the number of places you have to fix it). Not a big win for code duplicated twice, but a huge win for code duplicated 10 times.

I think functions also make code flow easier to follow mentally -- for example, I might write a 'void' function with no arguments for code that's only called once in the whole program. A waste of a function call? Sure, but it just makes it easy for me to visually separate unrelated blocks of code and have a nice bird's eye overview of what the sketch does in loop(). Pure personal preference, of course.

The nitpicking is not appreciated and discourages inexperienced programmers from asking for help.

Heh. Be glad PaulS hasn't replied yet! :wink:

5

[quote author=Matt Elias link=topic=189005.msg1398777#msg1398777 date=1379687806]So thanks for your help. The nitpicking is not appreciated and discourages inexperienced programmers from asking for help.
The helpful suggestions are very much appreciated! I will have learnt something new today.[/quote]

The "nitpicking" as you called it is what I would call "advice" :stuck_out_tongue:
How is an inexperienced programmer supposed to learn without getting feedback on his/her code?

I'm sorry I took the time and bothered to read your code fully, post [in my opinion] helpful suggestions and on top of it all provided a full code solution including comments. Won't happen again.

sigh

6

tylernt:
Pure personal preference, of course.

Mine, too.

7

tylernt:
Sure, but it just makes it easy for me to visually separate unrelated blocks of code and have a nice bird's eye overview of what the sketch does in loop(). Pure personal preference, of course.

I hear ya, how's this for bird's eye view.

void loop(){
  updateTempSensorReadings();
  if (debug > 0) checkMem(1,"loop");
}

int2str:
The "nitpicking" as you called it is what I would call "advice" :stuck_out_tongue:
How is an inexperienced programmer supposed to learn without getting feedback on his/her code?

I'm sorry I took the time and bothered to read your code fully, post [in my opinion] helpful suggestions and on top of it all provided a full code solution including comments. Won't happen again.

sigh

Maybe my reply was too hasty, I was feeling quite overwhelmed by everything I "was doing wrong", I probably took it all too personal. My reply has not meant as a personal attack either, just hoping to keep people interested in asking for help. I would like to someday submit my entire project for peer critique.

Your code reduced my memory footprint by more than 200 bytes (very nice).