Sortierung mit Abhängigkeit

[bogdan]

Angenommen ich hätte folgenden Text in einer StringList mit folgenden Werten:

D = C
A = D
C
B = A
F

Der Text soll dann so aussehen:

F
C
D = C
A = D
B = A

Dachte erst an 2 Schleifen, die eine liest das Schema und die andere prüft die Abhängigkeit. Vielleicht eine rekursive Function/Procedure?

[DeddyH]

Eigene Sortierungen erledigt man nach meiner Erfahrung am Besten mit TStringlist.CustomSort. Lieder habe ich das Schema Deiner Beispielsortierung nicht erkannt, sonst hätte ich einen Beispielcode posten können.

[bogdan]

Ich meine eine topologische Sortierung: http://de.wikipedia.org/wiki/Topologische_Sortierung

[DeddyH]

Sry, das ist mir momentan zu mathematisch

[JasonDX]

Das sollte recht einfach über eine rekursive Funktion machbar sein.
Du hast 2 Listen: Output und toPrint.

Output ist leer, toPrint ist die Liste der Elemente. Dann schreibst du eine Funktion, die im Endeffekt folgendes prüft:
Hat das Element keine Abhängigkeit? Dann gib das Element aus (sofern es noch nicht ausgegeben wurde)
Hat das Element eine Abhängigkeit? Gib erst die Abhängigkeit aus, dann das Element. - immer sofern es noch nicht ausgegeben wurde.

Code:

printElement(element):
  toPrint.remove(element)
  ist element ohne Anhängigkeiten?
    wenn element nicht in Output
      Output.add(element)
      return
  sonst // Element ist sowas wie A = B
    Abhängigkeit = parseAbhängigkeit(element); // parseAbhängigkeit würde bei (A = B) B zurückgeben.
    if output.contains(abhängigkeit) then
      return; // bereits ausgegeben
    if !toPrint.contains(abhängigkeit) then
      // FEHLER: zyklische Abhängigkeit
    printElement(findeElement(B)); // findeElement findet B in der Liste, und gibt B oder B = ... zurück, je nach dem was in der Liste steht.
    Output.add(element);

Wenn du dann

Code:

while (toPrint.size > 0) 
  printElement(toPrint.get(0))

aufrufst, ist in Output die sortierte Liste. Der Sauberkeithalber sollte man toPrint und Output als Parameter übergeben und nicht global definieren.
Wenn du mehr als 1 Abhängigkeit hast (bspw. A = B, C) dann gibt parseAbhängigkeit eine Liste zurück, über die Iteriert werden muss. Sonst ändert sich eig. nichts.
Und noch ne Anmerkung: Keine Garantie dass das funktioniert - reines Kopfkonstrukt.

[Elvis]

Zitat von JasonDX:

Und noch ne Anmerkung: Keine Garantie dass das funktioniert - reines Kopfkonstrukt.

Das ähnelt doch sehr dem Tarjan-Algo, sieht also gut aus.

[Uwe Raabe]

Zitat von bogdan:

F
C
D = C
A = D
B = A

Bis auf die Position von F kann ich das noch nachvollziehen. Da mit F aber keinerlei Abhängigkeiten bestehen, könnte es doch überall stehen, oder?

[himitsu]

Code:

schleife i (0 bis ende) -> laufe die Liste durch, von oben nach unten
  schleife j (i bis ende) -> schleife über alles, was noch nicht einsortiert wurde
    wenn element j von nichts oder nur von etwas über i abhängt
      dann tausche Elemente an i und j aus und erhöhe i -> also j hochschieben
    erhöhe j
  ende j
  wenn in schleife j nichts getauscht wurde
    dann exception, da nicht auflösbar -> Abhängiges fehlt oder Kreisreferenz
  erhöhe i
ende i

Man kann natürlich vorher erstmal alles ohne Abhängigkeit hochziehen, aber das ist von den Abhängikeiten her ja egal

Denn so ist es ja, im Grund, auch OK

Code:

C
D = C
A = D
B = A
F

[bogdan]

Uwe Raabe: Ja, die Werte ohne Abhängigkeit können theoretisch an beliebiger stelle stehen.

Ich versuche mal den Ansatz von JasonDX oder himitsu umzusetzen.