Zuerst einmal wünsche ich einen schönen Feiertag! 
Und bedanke mich an all jene, die sich die Zeit nehmen, mir zu helfen.
Ich möchte eine verlinkte Liste sortieren. Dabei ist aber die Art der Sortierung eine spezielle. Oder sogar, dynamische.
struct element{
int mainkey; //mk
int subkey; /sk
struct element *next;
};
Prinzipiell sollten alle Elemente nach mainkey sortiert werden, aber nur dann, wenn alle subkeys gleich sind. sind sie es nicht, sollen alle subkeys in teilgruppen eingeteilt werden, und diese gruppen dann nach mainkey sortiert. Daher ist es ein Sortieralgorithmus, welcher mit Mengen arbeitet.
mk1 = 1, sk1 = 0, mk2 = 2, sk2 = 0, mk3 = 3, sk3 = 0
mk4 = 4, sk4 = 0, mk5 = 5, sk5 = 0
sortierung:
mk1, mk2, mk3, mk4, mk5 (ok) - normaler sort-algo.
nun:
mk1 = 1, sk1 = 5, mk2 = 2, sk2 = 1, mk3 = 7, sk3 = 1
mk4 = 4, sk4 = 4, mk5 = 5, sk5 = 4
sortierung sollte so aussehen:
mk2, mk3, mk4, mk5, mk1
die liste wird erst zur laufzeit erstellt. vermutlich ist es einfacher, in die bereits sortierte liste einzufügen. sollte es aber einen algo für dieses problem geben, wäre es sehr interessant zu sehen, wie er aufgebaut ist. selbstverständlich kann es auch mehrere subkeys geben.. möchte mich aber zuerst mal auf einen beschränken..
vielleicht kennt sich jemand sehr gut mit sortieralgorithmen aus.. und kennt ein einfaches pattern.
meine adhoc lösung: teile die liste in teilgruppen (=suche nach subkeys, füge sie in partitionen, laufzeit ist aber dann n^2) sortiere teilgruppen (laufzeit je nach algo) und füge teilgruppen in sk reihenfolge wieder zusammen.
lg alex
(a.sk == b.sk && a.mk < b.mk). Sowas nennt man lexikographische Ordnung.