Sortieralgorithmus für Struktur-Daten

[Patrick L. (crashdemon)]

Hallo zusammen,

ich möchte gerne Daten (Energie) in einem Array sortieren, aber dabei 
die Information nicht verlieren welche Leistungsstufe die Energie 
umgesetzt hat.

Also konkret:

Leistungsstufe      Energie (kWh)
--------------------------------------
1                   12
2                   6
3                   7

Ich möchte nach der Energie sortieren. Also wäre das ja dann
6, 7, 12 (in der Reihenfolge). Jetzt habe ich die Energie ja aufsteigend 
sortiert, aber ich weiß ja nicht mehr welcher Leistungsstufe diese 
gehört.

Klar kann ich z.B. mit Quicksort ein Array sortieren, aber wie verliere 
ich die damit verknüpften Daten nicht? Was würdet ihr als bestes \ 
schnellsten Sortieralgorithmus für diese Fragestellung ansehen 
(Sortieralgo. am besten nicht rekursiv)?

[Timmo H. (masterfx)]

Du kannst quicksort auch auf Struct-Arrays anwenden ohne dass der 
Zusammenhang verloren geht

[Byteklöppler (Gast)]

Wenn der Index auch die Leistungsstufe darstellt: Wie willst du die 
Element-Reihenfolge überhaupt verändern, ohne diesen Zusammenhang zu 
verlieren? Was hat das mit einem spezifischen Algorithmus zu tun? Du 
könntest Leistungsstufe und Energie per Tupel oder Struct zusammenkleben 
und das Array dann sortieren (Energie). Über die verwendete 
Programmiersprache lässt du dich aber auch nicht aus ...

[Kai S. (kai1986)]

Hallo,

das geht mit jedem Sortieralgorithmus, du musst lediglich statt den 
einzelnen Werten ganze Zeilen tauschen/verschieben. Wenn deine Listen 
jetzt nicht gigantisch groß werden oder in einer extrem ineffizienten 
Sprache der Algorithmus implementiert wird dürfte die Laufzeit des 
Algorithmus kaum praktische Auswirkungen haben. Ansonsten hast du hier 
eine große Auswahl, je nach dem, wie viel Arbeit du investieren 
möchtest:
https://de.wikipedia.org/wiki/Sortierverfahren

Gruß Kai

[Daniel A. (daniel-a)]

JavaScript:

[
  [1,12],
  [2, 6],
  [3, 7]
].sort( (a,b) => a[1] - b[1] );

[Timmo H. (masterfx)]

Hier mal ein Minimalbeispiel:

typedef struct {
    int stufe;
    int energie;
}messwerte_t;

messwerte_t messwerte[] = { {1,12}, {2,6} .....

}

typedef int (*compfn)(const void*, const void*);

int messwerte_sort(messwerte_t *mess1,messwerte_t *mess2){

    if(mess1->energie < mess2->energie)
        return -1;
    else if(mess1->energie > mess2->energie)
        return 1;
    else
        return 0;
}

qsort((void *)messwerte,sizeof(messwerte)/sizeof(messwerte_t),sizeof(messwerte_t),(compfn)messwerte_sort);

[Yalu X. (yalu) (Moderator)]

Statt

int messwerte_sort(messwerte_t *mess1,messwerte_t *mess2){

    if(mess1->energie < mess2->energie)
        return -1;
    else if(mess1->energie > mess2->energie)
        return 1;
    else
        return 0;
}

kannst du wie in Daniels Beispiel auch einfach schreiben:

int messwerte_sort(messwerte_t *mess1,messwerte_t *mess2){
    return mess1->energie - mess2->energie;
}

da nur das Vorzeichen des Rückgabewerts dieser Funktion von Bedeutung
ist.

In Haskell geht's so:

sortOn snd [(1,12), (2,6), (3,7)]

Ergebnis:

[(2,6), (3,7), (1,12)]

:)

[Timmo H. (masterfx)]

Yalu X. schrieb:
> In Haskell geht's so:
> sortOn snd [(1,12), (2,6), (3,7)]
Was es alles für Programmiersprachen gibt... für mich ist C nach wie vor 
das einzig Wahre. Sowohl für µC als auch für Win GUIs, Linux etc.
Lua tue ich mir vielleicht noch an wegen dem ESP8266.

Gut der TO hat ja nicht gesagt welche Programmiersprache er verwendet. 
Von daher kann man ja auch Lösungswege in Fortran, ADA, Rust und Java 
posten

[Patrick L. (crashdemon)]

Danke schonmal für die Anworten. Ich würde das ganze gerne in Misra-C 
umsetzen (deswegen auch nicht rekursiv).

[Nop (Gast)]

Wieviele Leistungsklassen hast Du, und wie zeitkritisch ist deren 
Sortierung?

Wenn es nur drei sind, brauchst Du keinen Algorithmus, dann tun es 
Abfragen auch.

Bei 32 oder mehr wäre Shellsort die Lösung, wenn es auf die absolute 
Schnelligkeit ankommt. Ist eine geringe Varianz des Zeitbedarfs wichtig, 
dann ist Heapsort die Lösung. Beide sind ohne Rekursion. Hast Du 
allenfalls 8 Einträge, wäre Insertion-Sort die Antwort.

Gilt für bis zu 128 Einträge, was für embedded wohl die häufigste 
Situation sein dürfte. Zig Millionen Einträge hat man embedded 
schlichtweg nicht. In diesem Maßstab von Listengröße sind beide übrigens 
auch schneller als Quicksort.

Mein persönlicher Favorit ist Shellsort, und zwar mit der empirischen 
Folge nach Ciura.

Hier noch ein interessanter Quellenlink: 
http://embeddedgurus.com/stack-overflow/2009/03/sorting-in-embedded-systems/

[Patrick L. (crashdemon)]

Nop schrieb:
> Wieviele Leistungsklassen hast Du, und wie zeitkritisch ist deren
> Sortierung?

Es werden sechs Leistungsklassen sein, also nicht allzu viel.
Soll wie schon richtig erkannt auf einem embedded Controller laufen, 
deswegen auch Misra-C. Misra-C verbietet leider den Einsatz von 
Rekusionen, deswegen auch die Frage nach einem verfahren ohne 
Rekursion^^.

Ich habe mir mal den Link von dir angesehen. Da scheint ja InsertionSort 
das beste Verfahren für mein Aufgabe zu sein.

Ich müsste ja dann eh eine eigene Sortieralgorithmus-Funktion schreiben, 
da ich ja die Verknüpfung zwischen Energie und Leistungsklasse ja nicht 
verlieren will.

[Falk B. (falk)]

@Patrick L. (crashdemon)

>> Wieviele Leistungsklassen hast Du, und wie zeitkritisch ist deren
>> Sortierung?

>Es werden sechs Leistungsklassen sein, also nicht allzu viel.

Praktisch gar nix! Das ist Pille-Palle!

>Soll wie schon richtig erkannt auf einem embedded Controller laufen,
>deswegen auch Misra-C. Misra-C verbietet leider den Einsatz von
>Rekusionen, deswegen auch die Frage nach einem verfahren ohne
>Rekursion^^.

Nimm Bubble-Sort, das gehört zum kleinen 1x1 des Programmierens!

>Ich habe mir mal den Link von dir angesehen. Da scheint ja InsertionSort
>das beste Verfahren für mein Aufgabe zu sein.

Bei den paar Daten ist das vollkommen schnuppe.

>Ich müsste ja dann eh eine eigene Sortieralgorithmus-Funktion schreiben,
>da ich ja die Verknüpfung zwischen Energie und Leistungsklasse ja nicht
>verlieren will.

Mein Gott, bis du in der Programmierer-Grundschule? Ein 2D Array zu 
sortieren ist ja nun weiß Gott trivial!

[Nop (Gast)]

Falk B. schrieb:
> Nimm Bubble-Sort, das gehört zum kleinen 1x1 des Programmierens!

Ist auch bei den Datenmengen schlechter als Insertionsort, siehe den 
Link. Bubblesort ist IMMER schlecht.

Ansonsten programmiert man den Sortieralgorithmus halt ganz normal und 
tauscht außer den Sortierdaten auch die zweite Spalte des Arrays mit 
durch, bzw. das zweite Array, wenn man das separat hat.

Oder man hat ein Array mit Structs, die Leistungsklasse und Verbrauch 
als Komponenten haben. Die kann man mit tmp-struct und memcpy tauschen, 
oder, falls sich das speichermäßig ausgeht, kann man auch eine Union mit 
nem Basisdatentyp drüberlegen.

Vorlage gibt's übrigens hier:

https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#C

[Patrick L. (crashdemon)]

Hab da mal was herunter-gehackt. Scheint das zu machen was ich will. 
Danke an alle!

#include <stdio.h>
#include <iostream>

#define NUM_OF_RAILS 6

typedef enum
{
  RAIL_1 = 0,
  RAIL_2,
  RAIL_3,
  RAIL_4,
  RAIL_5,
  RAIL_6
} TRailId;

typedef struct  
{
  TRailId railId;
  unsigned int energy;
} TRailEnergy;

TRailEnergy RailEnergy[NUM_OF_RAILS];
 
void railEnergySort(TRailEnergy *railEnergy, unsigned int numRails) 
{
  
  for(unsigned int i = 1; i < numRails; ++i)
  {
    TRailEnergy tmpRailEnergy = railEnergy[i]; 
    unsigned int j = i;
    
    while((j > 0) && (tmpRailEnergy.energy < railEnergy[j - 1].energy)) 
    {
      railEnergy[j] = railEnergy[j - 1];
      --j;  
    }
    
    railEnergy[j] = tmpRailEnergy;
  } 
}
 
int main(int argc, char** argv) {
  // Init.
  RailEnergy[0].railId = RAIL_1;
  RailEnergy[0].energy = 230;
  
  RailEnergy[1].railId = RAIL_2;
  RailEnergy[1].energy = 254;
  
  RailEnergy[2].railId = RAIL_3;
  RailEnergy[2].energy = 0;
  
  RailEnergy[3].railId = RAIL_4;
  RailEnergy[3].energy = 90;
  
  RailEnergy[4].railId = RAIL_5;
  RailEnergy[4].energy = 90;  
  
  RailEnergy[5].railId = RAIL_6;
  RailEnergy[5].energy = 243;  
  
  // Algo.
    int i;
    for (i = 0; i < NUM_OF_RAILS; i++)
    {
        printf("%d \t %d\n", RailEnergy[i].railId, RailEnergy[i].energy); 
    }
    printf("\n\n");
        
    railEnergySort(RailEnergy, NUM_OF_RAILS);
    
    for (i = 0; i < NUM_OF_RAILS; i++)
    {
        printf("%d \t %d\n", RailEnergy[i].railId, RailEnergy[i].energy); 
    }
    printf("\n\n");
    
    return 0;
}

[Eric B. (beric)]

Patrick L. schrieb:
> void railEnergySort(TRailEnergy *railEnergy, unsigned int numRails)
> {
> ...
> }

Gratuliere zu deiner ersten Bubblesort-Implementierung ;-)

Hier eine Variante die etwas weiger hin und her kopiert:

void railEnergySort(TRailEnergy *railEnergy, unsigned int numRails)
{

  for(unsigned int i = 0; i < numRails - 1; ++i)
  {
    unsigned min = i;

    for(unsigned int j = i + 1; j < numRails; ++j)
    {
       if (railEnergy[j].energy < railEnergy[min].energy))
       {
          min = j;
       }
    }

    if (min != i)
    {
      TRailEnergy tmpRailEnergy = railEnergy[i];
      railEnergy[i] = railEnergy[min];
      railEnergy[min] = tmpRailEnergy;
    }
  }
}

[Patrick L. (crashdemon)]

Eric B. schrieb:
> Gratuliere zu deiner ersten Bubblesort-Implementierung ;-)

Ist eigentlich ein Insertion-Sort ;-)

[Nop (Gast)]

Patrick L. schrieb:
> Hab da mal was herunter-gehackt.

Kleine Anmerkung: wenn Du MISRA-Konformität möchtest, solltest Du auf 
Deklarationen mit "unsigned int" verzichten und einen geeigneten 
Datentypen aus stdint.h wählen.

Für die Energie ist offenbar uint32_t gemeint. Für die Schleifenzähler 
und min käme uint_fast8_t in Frage.

[Patrick L. (crashdemon)]

Nop schrieb:
> Kleine Anmerkung: wenn Du MISRA-Konformität möchtest, solltest Du auf
> Deklarationen mit "unsigned int" verzichten und einen geeigneten
> Datentypen aus stdint.h wählen.
>
> Für die Energie ist offenbar uint32_t gemeint. Für die Schleifenzähler
> und min käme uint_fast8_t in Frage.

Danke Nop für die Anmerkung. War nur ebend herunter-gehackt um zu 
zweigen das es läuft, die richtige Implementierung wird dann auch alle 
Misra belange berücksichtigen.