Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)?

[Der_Ventilator]

Hi, ich möchte einige Strings in eine logisch richtige Reihenfolge bringen (das das der Explorer ab WinXP auch macht).

Also nicht

bla-1-bla
bla-2-bla
bla-21-bla
bla-3-bla

(was ein 'normaler' Sortieralgorithmus, wie z.B. Quicksort, machen würde),

sondern

bla-1-bla
bla-2-bla
bla-3-bla
bla-21-bla

Im Grunde läuft alles darauf hinaus, nicht die < und > Vergleichsoperatoren von Delphi zu verwenden, sondern eine eigene isLower( , ):boolean Funktion zu schreiben.

Hab mir das so gedacht:

Haben die Strings 200 Zeichen, dann erstelle ich mir ein int-Array mit 200 Spalten und belege jede Zelle mit dem Ord( ) Wert der einzelnen Buchstaben des Strings und bei Zahlen (wenn mehrere Ziffern hintereinander stehen, zusammenfassen!) werden diese direkt hineingeschrieben; dann erfolgt solange Spaltenweise der Vergleich, bis ein Unterschied festzustellen ist.
Sind meine Überlegungen richtig bzw. hat schon eine solche Stringvergleichsprozedur geschrieben (die evtl schneller als meine ist)?

[tomsel]

Wie wäre es, den numerischen Teil vom Rest des Strings irgendwie zu trennen und nur, wenn bei der Zahl Gleichheit besteht, den Reststring zum Vergleich mit < > heranzuziehen?

[Der_Ventilator]

Das Problem ist, das die Strings nicht ganz so gleichförmig sind, wie ich es dargestellt habe:

Es geht um einen Mp3-Player, der Albumname + Tracknummer + Songtitel in einer Zeile ausgibt (id3 tag).

Nun sind ja die nichtnumerischen Teile nicht immer gleich lang (verschiedene Bandnamen usw). Deshalb müsse ich mir bei der Trennung dann noch zusätzlich die Position merken, wo die Zahlen ursprünglich waren, was ich mit meinen Spaltenindizes machen möchte.

[leddl]

Dann würde ich an deiner Stelle einfach den numerischen Teil aus den Strings auslesen und dann danach sortieren.

[Der_Ventilator]

Ich erstelle zur Zeit erst ein Liste aller Einträge.
Diese wird dann per Quicksort sortiert.
Nun sind da aber schon alle verschiedenen Alben bzw Bandnamen verarbeitet.
Wenn ich jetzt nur nach Nummern sortiere, reise ich mir doch die Alben auseinander.

Ich suche einfach eine schnelle Funktion, die 2 Strings nach oben genanneter Logik vergleicht.
Evtl. eine, die sogar ein 'Ü' als 'U' interpretiert.

[Der_Unwissende]

Hi,
benutz einfach ein wenig topologisches Sortieren (hoffe ich vertue mich da nicht mit dem Namen, die liegen schon zurück).
Pack einfach alle Tracks eines Albums (oder Interpreten oder was auch immer du als primäres Sortierkriterium hast) in je eine Liste ein.
Diese Liste Sortierst du dann nach dem sekundären Sortierkriterium (hier also die Tracknummer), dann bekommst du also sowas wie
1.
Album1-1 -> Album1-10 -> Album1-2...
Album2-1 -> Album2-10 -> Album2-2...
...
2.
Album1-1 -> Album1-2 -> Album1-10....
Album2-1 -> Album2-2 -> Album2-10....

Jetzt weißt du das die Listen jeweils richtig sortiert sind und muss nur noch in der Reihenfolge der Listen einfügen.

Gruß Der Unwissende

[leddl]

:gruebel: Meinst du vielleicht ein "stabiles" Sortierverfahren? :zwinker:
MergeSort wäre zB ne Möglichkeit. Das hat im übrigen auch bei großen Datenmengen ne bessere Laufzeit als dein Quicksort. Das hat nämlich im worst Case O(n²), MergeSort nur O(n*logn).

[alzaimar]

Grundsätzlich musst Du einfach nur eine Ordnung auf die Titel definieren. Das erreichst Du mit einer Funktion 'CompareTitle (a,b)', das für zwei Titel a und b einen Wert liefert, der angibt, ob a nun vor b, danach oder identisch mit b ist.

Das Sortierverfahren dürfte hier keine grosse Rolle spielen, denn ob nun Merge-, Quick-, Bubble-, Heap-, Shaker- oder was weiss ich was-Sort, Alle Verfahren bauen auf der o.g. Funktion auf.

Der 'topologische' Ansatz ist zwar vom Gedankengang richtig klassifiziert, aber topologisches Sortieren basiert auf Graphen, wobei ich nicht vorschlage, die Titelliste in einen Graphen zu übertragen. Es wäre wohl eher eine Unterteilung in Ebenen. Also, erst alle Titel in Albem unterteilen und dann jedes Album getrennt 'heuristisch-numerisch' sortieren. Anschließend die Alben noch (z.B. alphabetisch) sortieren. Vielleicht die Alben wieder in Genres und Musikstile unterteilen und dann sortieren etc.

Das *kann* man durchaus mit einem Sortiervorgang machen. Dazu musst du aber wissen, wo der Albentitel im String steckt. Hier mal ein ziemlich abstrakter Pseudocode für die zentrale Vergleichsfunktion:

Delphi-Quellcode:

Function CompareTitle (TitleA, TitleB : String) : Integer;
Var
  AlbumA, AlbumB : String;

Begin
  Result := CompareText (ExtractAlbumFromTitle (TitleA), ExtractAlbumFromTitle (TitleB));
  If Result<>0 Then Exit;
// Beide Titel sind vom selben Album
  Result := CompareText (ExtractSongNumberFromTitle (TitleA), ExtractSongNumberFromTitle (TitleB));
End;

Dann kannst Du alle Titel in eine Stringliste reinpacken und per CustomSort sortieren. Dieser Methode übergibst Du dann o.g. Funktion als Parameter. Ob die genauso aussehen muss, weiss ich nicht, aber wozu gibts die Online-Hilfe.

[leddl]

Zitat:

Zitat von alzaimar

Das Sortierverfahren dürfte hier keine grosse Rolle spielen, denn ob nun Merge-, Quick-, Bubble-, Heap-, Shaker- oder was weiss ich was-Sort, Alle Verfahren bauen auf der o.g. Funktion auf.

:shock: Also den Unterschied von QuickSort zu MergeSort merkst du bei entsprechend großen Datenmengen sehr wohl. Die Frage ist eben, wieviele Titel er in seiner Liste hat :zwinker:

Zitat:

Zitat von alzaimar

Der 'topologische' Ansatz ist zwar vom Gedankengang richtig klassifiziert, [...]

Wie gesagt, ich denke, er meinte ein stabiles Sortierverfahren, so daß ein erneutes Sortieren nach einem anderen Kriterium die Reihenfolge früherer Sortierkriterien beibehält.

[alzaimar]

Zitat:

Zitat von leddl

:shock: Also den Unterschied von QuickSort zu MergeSort merkst du bei entsprechend großen Datenmengen sehr wohl. Die Frage ist eben, wieviele Titel er in seiner Liste hat :zwinker:

Nee, is klar. Ich wollte eher auf die Erwähnung von Quicksort und Mergesort eingehen.

Aber: Vergleiche mal die Quick- mit Mergesort, wenn die Daten sich auf (langsamen) Datenträgern befinden (File Of TMyRecord). *Dann* merkst Du den Unterschied. Das Ergebnis wird aber nicht das sein, was Du erwartest.
Übrigens ist laut der grauen Theorie Mergesort im Gegensatz zu Quicksort vom Laufzeitverhalten auch im Worst-Case-Bereich optimal. Davon merkt man beim In-Memory-sortieren zwar Nichts, aber beim externen Sortieren sehr wohl: Dafür wurde Mergesort (Stichwort: Bänder) auch entwickelt.

Zitat:

Zitat von leddl

Zitat:

Zitat von alzaimar

Der 'topologische' Ansatz ist zwar vom Gedankengang richtig klassifiziert, [...]

Wie gesagt, ich denke, er meinte ein stabiles Sortierverfahren, so daß ein erneutes Sortieren nach einem anderen Kriterium die Reihenfolge früherer Sortierkriterien beibehält.

Das macht "Topologisches Sortieren"? Ich dachte immer, das sortiert nur einen Graphen. Welches Sortierverfahren behält 'die Reihenfolge früherer Sortierkriterien' nach erneutem 'Sortieren nach einem anderen Kriterium' bei? Ich kenne Datenstrukturen, die das machen, aber keine Sortierverfahren. Ach, auch egal. Wir wissen ja, was gemeint ist.