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
Du kannst quicksort auch auf Struct-Arrays anwenden ohne dass der Zusammenhang verloren geht
:
Bearbeitet durch User
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 ...
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
JavaScript:
1 | [
|
2 | [1,12], |
3 | [2, 6], |
4 | [3, 7] |
5 | ].sort( (a,b) => a[1] - b[1] ); |
Hier mal ein Minimalbeispiel:
1 | typedef struct { |
2 | int stufe; |
3 | int energie; |
4 | }messwerte_t; |
5 | |
6 | messwerte_t messwerte[] = { {1,12}, {2,6} ..... |
7 | |
8 | }
|
9 | |
10 | typedef int (*compfn)(const void*, const void*); |
11 | |
12 | int messwerte_sort(messwerte_t *mess1,messwerte_t *mess2){ |
13 | |
14 | if(mess1->energie < mess2->energie) |
15 | return -1; |
16 | else if(mess1->energie > mess2->energie) |
17 | return 1; |
18 | else
|
19 | return 0; |
20 | }
|
21 | |
22 | qsort((void *)messwerte,sizeof(messwerte)/sizeof(messwerte_t),sizeof(messwerte_t),(compfn)messwerte_sort); |
:
Bearbeitet durch User
Statt
1 | int messwerte_sort(messwerte_t *mess1,messwerte_t *mess2){ |
2 | |
3 | if(mess1->energie < mess2->energie) |
4 | return -1; |
5 | else if(mess1->energie > mess2->energie) |
6 | return 1; |
7 | else
|
8 | return 0; |
9 | }
|
kannst du wie in Daniels Beispiel auch einfach schreiben:
1 | int messwerte_sort(messwerte_t *mess1,messwerte_t *mess2){ |
2 | return mess1->energie - mess2->energie; |
3 | }
|
da nur das Vorzeichen des Rückgabewerts dieser Funktion von Bedeutung ist. In Haskell geht's so:
1 | sortOn snd [(1,12), (2,6), (3,7)] |
Ergebnis:
1 | [(2,6), (3,7), (1,12)] |
:)
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
Danke schonmal für die Anworten. Ich würde das ganze gerne in Misra-C umsetzen (deswegen auch nicht rekursiv).
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/
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.
@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!
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
Hab da mal was herunter-gehackt. Scheint das zu machen was ich will. Danke an alle!
1 | #include <stdio.h> |
2 | #include <iostream> |
3 | |
4 | #define NUM_OF_RAILS 6
|
5 | |
6 | typedef enum |
7 | {
|
8 | RAIL_1 = 0, |
9 | RAIL_2, |
10 | RAIL_3, |
11 | RAIL_4, |
12 | RAIL_5, |
13 | RAIL_6
|
14 | } TRailId; |
15 | |
16 | typedef struct |
17 | {
|
18 | TRailId railId; |
19 | unsigned int energy; |
20 | } TRailEnergy; |
21 | |
22 | TRailEnergy RailEnergy[NUM_OF_RAILS]; |
23 | |
24 | void railEnergySort(TRailEnergy *railEnergy, unsigned int numRails) |
25 | {
|
26 | |
27 | for(unsigned int i = 1; i < numRails; ++i) |
28 | {
|
29 | TRailEnergy tmpRailEnergy = railEnergy[i]; |
30 | unsigned int j = i; |
31 | |
32 | while((j > 0) && (tmpRailEnergy.energy < railEnergy[j - 1].energy)) |
33 | {
|
34 | railEnergy[j] = railEnergy[j - 1]; |
35 | --j; |
36 | }
|
37 | |
38 | railEnergy[j] = tmpRailEnergy; |
39 | }
|
40 | }
|
41 | |
42 | int main(int argc, char** argv) { |
43 | // Init.
|
44 | RailEnergy[0].railId = RAIL_1; |
45 | RailEnergy[0].energy = 230; |
46 | |
47 | RailEnergy[1].railId = RAIL_2; |
48 | RailEnergy[1].energy = 254; |
49 | |
50 | RailEnergy[2].railId = RAIL_3; |
51 | RailEnergy[2].energy = 0; |
52 | |
53 | RailEnergy[3].railId = RAIL_4; |
54 | RailEnergy[3].energy = 90; |
55 | |
56 | RailEnergy[4].railId = RAIL_5; |
57 | RailEnergy[4].energy = 90; |
58 | |
59 | RailEnergy[5].railId = RAIL_6; |
60 | RailEnergy[5].energy = 243; |
61 | |
62 | // Algo.
|
63 | int i; |
64 | for (i = 0; i < NUM_OF_RAILS; i++) |
65 | {
|
66 | printf("%d \t %d\n", RailEnergy[i].railId, RailEnergy[i].energy); |
67 | }
|
68 | printf("\n\n"); |
69 | |
70 | railEnergySort(RailEnergy, NUM_OF_RAILS); |
71 | |
72 | for (i = 0; i < NUM_OF_RAILS; i++) |
73 | {
|
74 | printf("%d \t %d\n", RailEnergy[i].railId, RailEnergy[i].energy); |
75 | }
|
76 | printf("\n\n"); |
77 | |
78 | return 0; |
79 | }
|
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:
1 | void railEnergySort(TRailEnergy *railEnergy, unsigned int numRails) |
2 | {
|
3 | |
4 | for(unsigned int i = 0; i < numRails - 1; ++i) |
5 | {
|
6 | unsigned min = i; |
7 | |
8 | for(unsigned int j = i + 1; j < numRails; ++j) |
9 | {
|
10 | if (railEnergy[j].energy < railEnergy[min].energy)) |
11 | {
|
12 | min = j; |
13 | }
|
14 | }
|
15 | |
16 | if (min != i) |
17 | {
|
18 | TRailEnergy tmpRailEnergy = railEnergy[i]; |
19 | railEnergy[i] = railEnergy[min]; |
20 | railEnergy[min] = tmpRailEnergy; |
21 | }
|
22 | }
|
23 | }
|
Eric B. schrieb: > Gratuliere zu deiner ersten Bubblesort-Implementierung ;-) Ist eigentlich ein Insertion-Sort ;-)
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.
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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.