Possible to sort an array of structs? (solved)

Projects General Guidance
1

I've got an array of structs, and I'd like to sort by the first element in the struct.

My struct looks like this:

struct event {
long seconds;
char event_type;
};

I'd like to sort by the seconds. Is there a way to do that without iterating through and building a new array?

Something like all_events.sort()?

Here's some stripped down sample code:

struct event {
  long seconds;
  char event_type; 
  };

event all_events[] = 
{
  {1, 'A'},
  {3, 'C'},
  {2, 'B'},
  {4, 'D'}
};

void setup() { 
  Serial.begin(115200);

  for(int i=0; i < sizeof all_events / sizeof all_events[0]; i++) 
  {  
    Serial.println(all_events[i].event_type);
  }
  
}

void loop() { 

}

I'd like this to print out "A, B, C, D".

Thanks for any help.

2

Aha, problem solved. For anyone else coming down this path, qsort() is your friend.

3

Hi,
I have the same Problem, could you please post your working code with qsort()? would be really helpful!
Thanks!!

4

Here's the code I used:

// used by qsort to sort an array
int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}


// sort the other_events, so the hour events are in the correct spot
l = sizeof(all_events) / sizeof(all_events[0]);
// qsort - last parameter is a function pointer to the sort function
qsort(all_events, l, sizeof(all_events[0]), cmpfunc);
5

Thank you, i dont really understand how.. but it works.

6

Normally, your comparison function would compare structure members, not just assume that the structure pointer points to the sort key.

7

Casting things to void * is very bad practice, because it undermines the entire type system of the language. This makes it very error prone, as demonstrated by the code in reply #3:
The elements being sorted are of type "event", but they are reinterpreted as integers in the cmpfunc. This is undefined behavior, and the code is broken, without the compiler even telling you. Even worse, you probably won't notice it at first.

The best solution is to use the C++ standard library function std::sort. This function is type-safe, and doesn't require you to cast anything to void * and back, and you don't have to manually enter the sizes of the array and its elements.

[color=#5e6d03]#include[/color] [color=#434f54]<[/color][b][color=#d35400]Arduino_Helpers[/color][/b][color=#434f54].[/color][color=#000000]h[/color][color=#434f54]>[/color]
[color=#5e6d03]#include[/color] [color=#434f54]<[/color][b][color=#d35400]AH[/color][/b][color=#434f54]/[/color][color=#000000]STL[/color][color=#434f54]/[/color][color=#000000]algorithm[/color][color=#434f54]>[/color]
[color=#5e6d03]#include[/color] [color=#434f54]<[/color][b][color=#d35400]AH[/color][/b][color=#434f54]/[/color][color=#000000]STL[/color][color=#434f54]/[/color][b][color=#d35400]iterator[/color][/b][color=#434f54]>[/color]

[color=#00979c]struct[/color] [color=#000000]event[/color] [color=#000000]{[/color]
  [color=#00979c]long[/color] [color=#000000]seconds[/color][color=#000000];[/color]
  [color=#00979c]char[/color] [color=#000000]event_type[/color][color=#000000];[/color]
[color=#000000]}[/color][color=#000000];[/color]

[color=#000000]event[/color] [color=#000000]all_events[/color][color=#000000][[/color][color=#000000]][/color] [color=#434f54]=[/color] [color=#000000]{[/color]
  [color=#000000]{[/color][color=#000000]1[/color][color=#434f54],[/color] [color=#00979c]'A'[/color][color=#000000]}[/color][color=#434f54],[/color]
  [color=#000000]{[/color][color=#000000]3[/color][color=#434f54],[/color] [color=#00979c]'C'[/color][color=#000000]}[/color][color=#434f54],[/color]
  [color=#000000]{[/color][color=#000000]2[/color][color=#434f54],[/color] [color=#00979c]'B'[/color][color=#000000]}[/color][color=#434f54],[/color]
  [color=#000000]{[/color][color=#000000]4[/color][color=#434f54],[/color] [color=#00979c]'D'[/color][color=#000000]}[/color]
[color=#000000]}[/color][color=#000000];[/color]

[color=#00979c]void[/color] [color=#5e6d03]setup[/color][color=#000000]([/color][color=#000000])[/color] [color=#000000]{[/color]
  [b][color=#d35400]Serial[/color][/b][color=#434f54].[/color][color=#d35400]begin[/color][color=#000000]([/color][color=#000000]115200[/color][color=#000000])[/color][color=#000000];[/color]
  [color=#5e6d03]while[/color][color=#000000]([/color][color=#434f54]![/color][b][color=#d35400]Serial[/color][/b][color=#000000])[/color][color=#000000];[/color]

  [color=#00979c]auto[/color] [color=#000000]cmpfunc[/color] [color=#434f54]=[/color] [color=#000000][[/color][color=#000000]][/color][color=#000000]([/color][color=#000000]event[/color] [color=#000000]a[/color][color=#434f54],[/color] [color=#000000]event[/color] [color=#000000]b[/color][color=#000000])[/color] [color=#000000]{[/color] [color=#5e6d03]return[/color] [color=#000000]a[/color][color=#434f54].[/color][color=#000000]seconds[/color] [color=#434f54]<[/color] [color=#000000]b[/color][color=#434f54].[/color][color=#000000]seconds[/color][color=#000000];[/color] [color=#000000]}[/color][color=#000000];  [/color]
  [color=#000000]std[/color][color=#434f54]:[/color][color=#434f54]:[/color][color=#000000]sort[/color][color=#000000]([/color][color=#000000]std[/color][color=#434f54]:[/color][color=#434f54]:[/color][color=#d35400]begin[/color][color=#000000]([/color][color=#000000]all_events[/color][color=#000000])[/color][color=#434f54],[/color] [color=#000000]std[/color][color=#434f54]:[/color][color=#434f54]:[/color][color=#d35400]end[/color][color=#000000]([/color][color=#000000]all_events[/color][color=#000000])[/color][color=#434f54],[/color] [color=#000000]cmpfunc[/color][color=#000000])[/color][color=#000000];[/color]

  [color=#5e6d03]for[/color][color=#000000]([/color][color=#000000]event[/color] [color=#000000]e[/color] [color=#434f54]:[/color] [color=#000000]all_events[/color][color=#000000])[/color]
    [b][color=#d35400]Serial[/color][/b][color=#434f54].[/color][color=#d35400]println[/color][color=#000000]([/color][color=#000000]e[/color][color=#434f54].[/color][color=#000000]event_type[/color][color=#000000])[/color][color=#000000];[/color]
[color=#000000]}[/color]

[color=#00979c]void[/color] [color=#5e6d03]loop[/color][color=#000000]([/color][color=#000000])[/color] [color=#000000]{[/color][color=#000000]}[/color]

If you are using an ARM or Espressif Arduino, this function is available out of the box, you can just #include and #include .
If you are on AVR, you can use the Arduino Helpers library (this also works on ARM and Espressif).

Pieter

8

auto cmpfunc = [](event a, event b) { return a.seconds < b.seconds; }; It may be safe and all that good stuff, but damn! It is UGLY!
I think after template syntax, lambda function syntax is my least favourite. :smiley:

9

Here you go :slight_smile: :

#include <Arduino_Helpers.h>
#include <AH/STL/algorithm>
#include <AH/STL/iterator>

struct event {
  long seconds;
  char event_type;
};

event all_events[] = {
  {1, 'A'},
  {3, 'C'},
  {2, 'B'},
  {4, 'D'}
};

bool cmpfunc(event a, event b) { 
  return a.seconds < b.seconds; 
}

void setup() {
  Serial.begin(115200);
  while(!Serial);

  std::sort(std::begin(all_events), std::end(all_events), cmpfunc);

  for(event e : all_events)
    Serial.println(e.event_type);
}

void loop() {}