entscheidungsbaum merge-sort
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
fehler im heun?
hi,
ich will ja die informatik-goetter nicht erzuernen, aber kann es sein, dass im heun-buch auf seite 73 fehler sind?
da ist der entscheidungsbaum fuer merge-sort aufgezeichnet und in der wurzel wird 1,2 verglichen. im linken zweig hat man ja dann das ergebnis, dass 1 < 2. also muesste in jedem blatt die 1 links von der 2 stehen. das tut sie aber in fuenf faellen nicht!
haben wir da was falsch verstanden (andere haben dasselbe problem), oder ist das wirklich falsch? meinungen dazu?
gruesse,
-steppenwolf
Der Entscheidungsbaum waere fuer 2 Listen mit 2 Elementen eh viel zu gross. Die ersten beiden Fragen ( [1,2] und [3,4] ) entscheiden, wie die beiden listen geordnet sind. Ganz links/links [12] [34] links/rechts [12] [43] rechts/links [21] [34] und rechts/rechts [21] [43]. Alles was nach den ersten 2 Vergleichen ist ist der Merge-Baum auf den 2 Listen, die von ersten 2 Vergleichen bestimmt wurden. Das ist dann auch das was in der Uebung dran war.
Hast du das jetzt verstanden so konfus wie ich das erklaert hab? Hoffe mal…
hmm,
verstanden habe ich das schon, denke ich. aber was soll das?
ich bezeichne halt einfach das erste element der ersten liste mit 1 und nicht wahlweise auch mit 2, was ich dann vorher nochmal abpruefen muss.
oder habe ich es doch falsch verstanden?
Die zugrundeliegende Eingabefolge ist also die inverse Permutation zur Permutation im Entscheidungsbaum auf Seite 73.
Beispiel: das 5. Blatt von links:
(2 4 1 3)[sup]-1[/sup] = (3 1 4 2)
Damit ist dann (2 4 1 3) * (3 1 4 2) = (1 2 3 4) die aufsteigend sortierte Folge.
hmm,
aber auf den punkt gebracht: ist das fuer uns relevant, also muessen unsere entscheidungsbaeume so aussehen oder koennen wir die einfacher machen, indem wir die anfangselemente mit [1234] bezeichnen und dann die entsprechenden vergleiche und ergebnisse hinschreiben?