Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Liste "in sich" nochmals sortieren
galagher - Fr 01.02.13 16:46
Titel: Liste "in sich" nochmals sortieren
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:
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:
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?
jfheins - Fr 01.02.13 16:57
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 - 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.
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
end |
Vorzeichen nach Geschmack vertauschen, ich kann mir nie merken wierum der Standardrückgabewert bei den Dingern ist :P
€: yay, ich hab auch mal ein Rennen gewonnen :mrgreen: Wobei meins glaub ich eher FPC ist. Generic Lists und so.
MeierZwoo - 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:
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):
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
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))
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 - 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.
MeierZwoo - Sa 02.02.13 08:03
| galagher hat folgendes geschrieben : |
| Wenn ich statt der Monatsnamen entsprechende Zahlen verwende, |
Wie denn sonst?
galagher - Sa 02.02.13 10:54
| MeierZwoo hat folgendes geschrieben : |
| Wie denn sonst? |
Ich meine, statt:
ist das eben:
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!
WasWeißDennIch - Sa 02.02.13 12:21
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 - Sa 02.02.13 13:55
| galagher hat folgendes geschrieben : |
| MeierZwoo hat folgendes geschrieben : | | Wie denn sonst? |
Ich meine, statt:
|
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 - Sa 02.02.13 14:16
Wieso soll man denn alles Mögliche in einen String konvertieren? Nur damit man mit einer TStringlist sortieren kann?
MeierZwoo - 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 - Sa 02.02.13 14:32
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 - 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 - Sa 02.02.13 15:00
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 - Sa 02.02.13 15:13
Wo bekommst Du bei "adddata" den Ordinalwert des Monats plötzlich her?
WasWeißDennIch - Sa 02.02.13 15:17
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 - 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 - Sa 02.02.13 16:02
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 - 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 :)
WasWeißDennIch - Sa 02.02.13 16:33
Sieht so aus.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!