Forum: PC-Programmierung Sortieralgorithmus für Struktur-Daten


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Patrick L. (crashdemon)


Bewertung
0 lesenswert
nicht lesenswert
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)?

: Bearbeitet durch User
von Timmo H. (masterfx)


Bewertung
1 lesenswert
nicht lesenswert
Du kannst quicksort auch auf Struct-Arrays anwenden ohne dass der 
Zusammenhang verloren geht

: Bearbeitet durch User
von Byteklöppler (Gast)


Bewertung
1 lesenswert
nicht lesenswert
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 ...

von Kai S. (kai1986)


Bewertung
1 lesenswert
nicht lesenswert
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

von Daniel A. (daniel-a)


Bewertung
2 lesenswert
nicht lesenswert
JavaScript:

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


von Timmo H. (masterfx)


Bewertung
3 lesenswert
nicht lesenswert
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);


: Bearbeitet durch User
von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
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)]

:)

von Timmo H. (masterfx)


Bewertung
0 lesenswert
nicht lesenswert
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

: Bearbeitet durch User
von Patrick L. (crashdemon)


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

von Nop (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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/

von Patrick L. (crashdemon)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Falk B. (falk)


Bewertung
0 lesenswert
nicht lesenswert
@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!

von Nop (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Patrick L. (crashdemon)


Bewertung
0 lesenswert
nicht lesenswert
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;
}

von Eric B. (beric)


Bewertung
0 lesenswert
nicht lesenswert
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;
    }
  }
}

von Patrick L. (crashdemon)


Bewertung
0 lesenswert
nicht lesenswert
Eric B. schrieb:
> Gratuliere zu deiner ersten Bubblesort-Implementierung ;-)

Ist eigentlich ein Insertion-Sort ;-)

von Nop (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Patrick L. (crashdemon)


Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.