Liste "in sich" nochmals sortieren

galagher · Verfasst: Fr 01.02.13 16:46

Hallo!

Ich möchte eine Liste aufsteigend sortieren, die aus Jahren und Monatsnamen besteht. Momentan ist die Liste bloss nach Jahren sortiert und sieht so aus:

markieren

Quelltext

1:
2:
3:
4:
5:
6:

2009 August
2009 Mai
2013 Dezember
2013 Jänner
2014 Dezember
2016 Jänner

Ich möchte diese Liste aber auch "in sich" sortieren, also zunächst nach Jahren, dann, "innerhalb" der Jahre nach Monaten, so dass das so aussieht:

markieren

Quelltext

1:
2:
3:
4:
5:
6:

2009 Mai
2009 August
2013 Jänner
2013 Dezember
2014 Dezember
2016 Jänner

Das ist nur ein Beispiel, die Liste kann im Prinzip beliebig lang sein und alle möglichen Jahre und Monate in allen möglichen Kombinationen enthalten.

Frage also: Wie sortiere ich das? Mein erster Gedanke wäre hier:
Merke dir die Jahre, entferne sie, sortiere die Liste alphabetisch nach Monaten, füge dann die Jahre wieder vorne an. Wiederhole das für alle Jahre.
Aber geht das auch einfacher?

_________________
gedunstig war's - und fahle wornen zerschellten karsig im gestrock. oh graus, es gloomt der jabberwock - und die graisligen gulpen nurmen!

jfheins · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

Wenn du einen stabilen Sortieralgorithmus verwendest, kannst du einfach die gesamte Liste zweimal nach unterschiedlichen Kriterien sortieren.
==> http://de.wikipedia.org/wiki/Stabilität_(Sortierverfahren)

Martok · Verfasst: Fr 01.02.13 17:03

Oder du änderst deine Komparatorfunktion (kommt drauf an, wie du sortierst) so, dass sie das tut, was du möchtest. Also z.b.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

function CompareKeys(A,B: TListElement): integer;
begin
  Result:= A.Jahr-B.Jahr;
  if Result = 0 then
    Result:= A.Monat-B.Monat;
  if Result = 0 then
    // Tag, Stunde, Minute... etc ;-)
end

Vorzeichen nach Geschmack vertauschen, ich kann mir nie merken wierum der Standardrückgabewert bei den Dingern ist

€: yay, ich hab auch mal ein Rennen gewonnen :mrgreen:

Wobei meins glaub ich eher FPC ist. Generic Lists und so.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

WasWeißDennIch · Beiträge: 653 Erhaltene Danke: 160

Wenn es sich um TList oder einen Nachfahren davon handelt, gibt es ja einen Callback (Vergleichsfunktion) vom Typ TListSortCompare. Innerhalb dessen kann man unterschiedliche Kriterien auswerten.

[edit] Einen Hauch zu spät, aber derselbe Gedanke :mrgreen:

[/edit]

MeierZwoo · Verfasst: Fr 01.02.13 21:57

Irgendwo hängen bei mir in alten Quellcodes noch ein paar Sortieralgorithmen rum, aber bei neuem Code (bzw. Ergänzungen) bin ich zu faul geworden, mir deswegen einen Kopf zu machen - und bei den fetten CPUs und RAMs ist sortieren über TStringList nicht mehr zeitkritisch. Deshalb sortiere ich nur noch über TStringList und habe dafür (und andere Anwendungen) in allen Programmen ein bis zwei Listen vom Programmstart bis Ende zur allgemeinen Verfügung.

Ich cleare die Liste, erstelle aus den ankommenden Daten einen String mit dem Sortierkriterium und schreibe die Originaldaten an eine bestimmte Lesestelle dahinter und lese aus der sortierten Liste die Originaldaten wieder aus:

Daten unsortiert:

markieren

Quelltext

1:
2:
3:
4:
5:
6:

Ute 23. August 2009
Peter 4. Dezember 2014 
Paul 12. Mai 2009
Hans 12. Januar 2013 
Rita 13. Januar 2016
Klaus 3. Dezember 2013

Nach Sortierkriterien und sortierbaren Kriterien (hier Kalenderdatum) mit Original in eine List1:StringList geschrieben (Die leerstellen zwischen Sortierwert und Original können auch unterbleiben):

markieren

Quelltext

1:
2:
3:
4:
5:
6:

20090823      Ute 23. August 2009
20141204      Peter 4. Dezember 2014 
20090512      Paul 12. Mai 2009
20130112      Hans 12. Januar 2013 
20160113      Rita 13. Januar 2016
20131203      Klaus 3. Dezember 2013

List1.sort

markieren

Quelltext

1:
2:
3:
4:
5:
6:

20090512      Paul 12. Mai 2009
20090823      Ute 23. August 2009
20130112      Hans 12. Januar 2013
20131203      Klaus 3. Dezember 2013
20141204      Peter 4. Dezember 2014 
20160113      Rita 13. Januar 2016

Original wieder ausgelesen (copy(List1[n],Lesestelle,Laenge))

markieren

Quelltext

1:
2:
3:
4:
5:
6:

Paul 12. Mai 2009
Ute 23. August 2009
Hans 12. Januar 2013
Klaus 3. Dezember 2013
Peter 4. Dezember 2014 
Rita 13. Januar 2016

Das ist zwar nicht die hohe Schule der Programmierung, aber benötigt nur geringen Zeitaufwand und ist auch nicht unbedingt resourcen-fressender als ein rekursiver Algorithmus.

Die sog. Stabilität läßt sich bei Bedarf durch einen Reihenfolgeanhang am Sortierbegriff auch einhalten.

Zum Zeitverhalten: Ich habe bei einer speziellen Routine, die neben Berechnungen zig dieser Sortierungen pro Aufruf benutzt, das Zeitverhalten nur durch 10.000.000 mal aufrufen messen können (0,0001 bis 0,0007 s für die gesamte Routine). Bei den Werten bleib ich auf der auch in 10 Jahren im Quellcode nachvollziehbaren Methode mit den Listen

galagher · Verfasst: Sa 02.02.13 07:36

MeierZwoo hat folgendes geschrieben :

- und bei den fetten CPUs und RAMs ist sortieren über TStringList nicht mehr zeitkritisch. Deshalb sortiere ich nur noch über TStringList

Ja, ich sortiere das auch mit einer TStringList.
Bin aber draufgekommen, dass es zumindest für meinen Fall noch einfacher geht: Wenn ich statt der Monatsnamen entsprechende Zahlen verwende, genügt eine einfaches .Sort! Danach tausche ich die Monatszahlen einfach gegen Monatsnamen aus.

_________________
gedunstig war's - und fahle wornen zerschellten karsig im gestrock. oh graus, es gloomt der jabberwock - und die graisligen gulpen nurmen!

MeierZwoo · Verfasst: Sa 02.02.13 08:03

galagher hat folgendes geschrieben :

Wenn ich statt der Monatsnamen entsprechende Zahlen verwende,

Wie denn sonst?

galagher · Verfasst: Sa 02.02.13 10:54

MeierZwoo hat folgendes geschrieben :

Wie denn sonst?

Ich meine, statt:

markieren

Quelltext

1:

2009 Mai

ist das eben:

markieren

Quelltext

1:

2009 05

Dann genügt eine einfache aufsteigende Sortierung, wie sie zB. Sort bei TStringList bietet. Ich habe dabei den Vorteil, dass zunächst sowieso nur Zahlen in die Liste geschrieben werden und ich erst danach die Monats-Zahlen durch Monatsnamen ersetze. Ich habe das zuerst übersehen, da es ein altes Projekt ist, das ich jetzt wieder hervorgekramt habe!
Also: Erst die (temporäre) TStringList befüllen, danach sortieren, dann den Inhalt in eine TListBox schreiben und die TStringList wieder freigeben. Das ist alles!

_________________
gedunstig war's - und fahle wornen zerschellten karsig im gestrock. oh graus, es gloomt der jabberwock - und die graisligen gulpen nurmen!

WasWeißDennIch · Beiträge: 653 Erhaltene Danke: 160

Irgendwie ist das aber eher Sortierung der Darstellung statt der eigentlichen Daten. In diesem Fall ist das noch relativ einfach zu machen, wird aber bei komplexeren Daten schnell kompliziert und unhandlich.

MeierZwoo · Verfasst: Sa 02.02.13 13:55

galagher hat folgendes geschrieben :

MeierZwoo hat folgendes geschrieben :

Wie denn sonst?

Ich meine, statt:

markieren

Quelltext

1:

2009 Mai

markieren

Quelltext

1:

2009 05

Ich meinte mit "Wie denn sonst?" wie bitte willste du Monatsnamen nach Zeit sortieren, ohne sie in Ordinalwerte umzuwandeln? Es ist doch total selbstverständlich, solchen Sortierbegriffen wie Monatsnamen, Wochentagen ... erst Ordinalwerte zuzuordnen.

WasWeißDennIch hat folgendes geschrieben :

Irgendwie ist das aber eher Sortierung der Darstellung statt der eigentlichen Daten. In diesem Fall ist das noch relativ einfach zu machen, wird aber bei komplexeren Daten schnell kompliziert und unhandlich.

Ich will weder meine Methode durchpauken noch jemanden dazu überreden - aber benenn mal bitte irgend etwas, was sich nicht durch ein sortierbares Stringlateral darstellen läßt - entweder durch direkte Umwandlung oder Umwandlung in einen Wert. Und wenn dies nicht geht, wie machst Du dann in einem Sortier-Algorithmus den Größenvergleich?

WasWeißDennIch · Beiträge: 653 Erhaltene Danke: 160

Wieso soll man denn alles Mögliche in einen String konvertieren? Nur damit man mit einer TStringlist sortieren kann?

MeierZwoo · Verfasst: Sa 02.02.13 14:28

WasWeißDennIch hat folgendes geschrieben :

Wieso soll man denn alles Mögliche in einen String konvertieren? Nur damit man mit einer TStringlist sortieren kann?

Ich hatte dich gebeten, etwas zu benennen, was sich weder durch Konvertierung noch Darstellung mittels eines Ordinalwertes darstellen läßt. Und auch gebeten, dann zu erklären, wie Du dann damit den Größenvergleich innerhalb eines Sortieralgorithmus machst. - Mir jedenfalls fällt nichts ein und ist auch noch nichts untergekommen.

WasWeißDennIch · Beiträge: 653 Erhaltene Danke: 160

Und ich hatte Dich gebeten, mir zu erklären, wieso Du erst in einen String konvertieren willst. Sind wir uns eben gegenseitig eine Antwort schuldig.

MeierZwoo · Verfasst: Sa 02.02.13 14:48

WasWeißDennIch hat folgendes geschrieben :

Und ich hatte Dich gebeten, mir zu erklären, wieso Du erst in einen String konvertieren willst.

Ohne in einen String zu konvertieren kann man nunmal nichts in eine StringList eintragen.

Und weshalb ich per StringList sortiere, hatte ich in meinem Beitrag, auf den Du dich ja beziehst, ausführlich gesagt.

Was daran unhandlich sein soll, entzieht sich meiner Kenntnis. Vorallem in Hinblick auf Nachvollziehbarkeit im Quellcode, auch nach 10 Jahren noch, ist es genau das Gegenteil von unhandlich.

WasWeißDennIch · Beiträge: 653 Erhaltene Danke: 160

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:

type
  TMonat = 1..12;

  PMyItem = ^TMyItem;
  TMyItem = record
    Jahr: Cardinal;
    Monat: TMonat;
  end;

...

function SortCompare(Left, Right: PMyItem): integer;
begin
  Result := Left^.Jahr - Right^.Jahr;
  if Result = 0 then
    Result := Left^.Monat - Right^.Monat;
end;

function TForm1.ItemToString(const Item: TMyItem): string;
const
  sMonate: array[TMonat] of string = ('Januar', 'Februar', 'März', 'April', 'Mai',
    'Juni', 'Juli', 'August', 'September', 'Oktober', 'November', 'Dezember');
begin
  Result := Format('%s %d', [sMonate[Ord(Item.Monat)], Item.Jahr]);
end;

procedure TForm1.AddData(Jahr: Cardinal; Monat: TMonat; List: TList);
var
  Item: PMyItem;
begin
  Assert(Assigned(List));
  New(Item);
  Item^.Jahr := Jahr;
  Item^.Monat := Monat;
  List.Add(Item);
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Daten: TList;
begin
  Daten := TList.Create;
  try
    AddData(2009, 11, Daten);
    AddData(2009, 12, Daten);
    AddData(2009, 9, Daten);
    AddData(2009, 4, Daten);
    AddData(2009, 7, Daten);
    AddData(2013, 3, Daten);
    AddData(2009, 3, Daten);
    AddData(2009, 10, Daten);
    AddData(2009, 1, Daten);
    AddData(2009, 9, Daten);
    AddData(2000, 11, Daten);
    AddData(2010, 7, Daten);
    AddData(2002, 9, Daten);
    AddData(2012, 2, Daten);
    Daten.Sort(@SortCompare);
    ListData(Daten, Listbox1.Items);
  finally
    Daten.Free;
  end;
end;

procedure TForm1.ListData(List: TList; Output: TStrings);
var
  i: integer;
begin
  Assert(Assigned(List) and Assigned(Output));
  Output.BeginUpdate;
  try
    Output.Clear;
    for i := 0 to List.Count - 1 do
      Output.Add(ItemToString(TMyItem(List[i]^)));
  finally
    Output.EndUpdate;
  end;
end;

Das kommt mit einer einzigen Liste aus, benötigt außer bei der Darstellung keine Konvertierung, man muss sich keine Gedanken machen, wie der String für eine korrekte Sortierung auszusehen hat (führende Nullstellen), etc. Unter Verwendung von Generics wäre es noch einen Tick einfacher, ich habe hier bewusst darauf verzichtet.

MeierZwoo · Verfasst: Sa 02.02.13 15:13

Wo bekommst Du bei "adddata" den Ordinalwert des Monats plötzlich her?

WasWeißDennIch · Beiträge: 653 Erhaltene Danke: 160

OK, ich hatte im Ausgangspost überlesen, dass es sich um Monatsnamen handelt. Dann schreiben wir eben eine Funktion mehr und machen die Array-Konstante global, spielt aber für das grundsätzliche Vorgehen keine Rolle.

MeierZwoo · Verfasst: Sa 02.02.13 15:58

WasWeißDennIch hat folgendes geschrieben :

spielt aber für das grundsätzliche Vorgehen keine Rolle.

... außer, daß eben das, was Du unbedingt vermeiden willst, eine Konvertierung (hier zu einem Ordinalwert) eben doch durchgeführt werden muß. Die vergleichbaren Sortierbegriffe/Werte müssen nun einmal größenvergleichbar vorbereitet bzw. als solche definiert werden, egal womit man sortiert.

Und nochmal: Ich habe mehrfach ausdrücklich betont, daß ich niemanden zur Benutzung von StringLists überreden will. Ich benutze diese.

Nur was an deinem Beispiel handlicher und evtl. auch resoercenschonender sein soll, entzieht sich nun wirklich meiner Kenntnis. Es ist deine Art, eine Aufgabe zu programmieren.

Für mich ist wesentlich, auch nach 25 Jahren meinen eigenen Quellcode schnell verstehen zu können.

WasWeißDennIch · Beiträge: 653 Erhaltene Danke: 160

Was Du machst, geht mir auch irgendwo hinten vorbei. Ich hatte lediglich darauf hingewiesen, dass hier eine Darstellung sortiert wird und nicht die dahinterstehenden Daten. Wenn Du daraus eine Diskussion anzettelst, ist das Deine Sache.

[edit] Außerdem hatte ich nie behauptet, Konvertierungen unbedingt vermeiden zu müssen/wollen, aber ich muss das je Item nur einmal machen, nämlich beim Einfügen in die Liste. Und dass eine einzelne Liste weniger Ressourcen verbraucht als deren 2 sollte irgendwo logisch sein, oder? [/edit]

MeierZwoo · Verfasst: Sa 02.02.13 16:30

WasWeißDennIch hat folgendes geschrieben :

Was Du machst, geht mir auch irgendwo hinten vorbei.

Dann sind wir ja wenigsten in einem Punkt gleicher Meinung

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme