inf-schule | Die Komplexität des Sortierproblems » Beschreibung von Sortiervorgängen mit Entscheidungsbäumen

Beschreibung von Sortiervorgängen mit Entscheidungsbäumen

Mögliche Anordnungen beim Sortieren

Wir beginnen die Überlegungen mit Untersuchungen zu Listen der Länge 4. Gegeben ist eine Liste L = [a, b, c, d] mit 4 Elementen (z.B. Zahlen) und eine Vergleichsoperation, über die die Listenelemente sortiert werden sollen.

Bei einer Liste mit 4 Elementen gibt es 24 verschiedene Möglichkeiten, wie die Listenelemente nach der Sortierung angeordnet sein können.

Aufgabe 1

(a) Findest du alle diese 24 Möglichkeiten?

abcd,abdc,acbd,...

(b) Wie viele Möglichkeiten gibt es bei Listen mit 3, 5, 6, 7, ... Listenelementen? Kannst du die Anzahl mit einer allgemeinen Formel beschreiben?

Darstellung eines Sortiervorgangs mit einem Entscheidungsbaum

Das folgende Baumdiagramm beschreibt die möglichen Ausführungen des Algorithmus selectionsort. Es sind die zum jeweiligen Ausführzeitpunkt vorliegende Liste und die dann durchzuführenden Entscheidungen angegeben. Jeder Vergleich ergibt eine Fallunterscheidung, die hier durch T(rue) und F(alse) und eine entsprechende Einrückung dargestellt ist. In den geschweiften Klammern {...} sind die Anordnungen der Listenelemente aufgeführt, die in den jeweiligen Fällen noch möglich sind. Zu Beginn sind es alle denkbaren Anordnungen, nach den Fallunterscheidungen spaltet sich die Menge der möglichen Anordnungen auf. Wenn alle Fallunterscheidungen abgearbeitet sind, müssen auch alle denkbaren Anordnungen gefunden sein.

Klicke auf die hell markierten Bedingungen, um den jeweiligen Unterbaum zu öffnen. Du kannst den Baum auch ganz öffnen bzw. schließen.

{abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca,
          cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcba}

[a, b, c, d]
a < b?

T: {abcd,abdc,acbd,acdb,adbc,adcb,cabd,cadb,cdab,dabc,dacb,dcab}
[a, b, c, d]
a < c?
- T: {abcd,abdc,acbd,acdb,adbc,adcb,dabc,dacb}
  [a, b, c, d]
  a < d?
  - T: {abcd,abdc,acbd,acdb,adbc,adcb}
    [a, b, c, d]
    b < c?
    - T: {abcd,abdc,adbc}
      [a, b, c, d]
      b < d?
      - T: {abcd,abdc}
        [a, b, c, d]
        c < d?
        
        T: {abcd}
        [a, b, c, d]
        
        F: {abdc}
        [a, b, d, c]
      - F: {adbc}
        [a, d, c, b]
        c < b?
        
        T: {}
        [a, d, c, b]
        
        F: {adbc}
        [a, d, b, c]
    - F: {acbd,acdb,adcb}
      [a, b, c, d]
      c < d?
      - T: {acbd,acdb}
        [a, c, b, d]
        b < d?
        
        T: {acbd}
        [a, c, b, d]
        
        F: {acdb}
        [a, c, d, b]
      - F: {adcb}
        [a, d, c, b]
        c < b?
        
        T: {adcb}
        [a, d, c, b]
        
        F: {}
  - F: {dabc,dacb}
    [d, b, c, a]
    b < c?
    - T: {dabc}
      [d, b, c, a]
      b < a?
      - T: {}
        c < a?
        
        T: {}
        
        F: {}
      - F: {dabc}
        [d, a, c, b]
        c < b?
        
        T: {}
        
        F: {dabc}
        [d, a, b, c]
    - F: {dacb}
      [d, b, c, a]
      c < a?
      - T: {}
        b < a?
        
        T: {}
        
        F: {}
      - F: {dacb}
        [d, a, c, b]
        c < b?
        
        T: {dacb}
        [d, a, c, b]
        
        F: {}
- F: {cabd,cadb,cdab,dcab}
  [a, b, c, d]
  a < d?
  - T: {cabd,cadb}
    [a, b, c, d]
    b < c?
    - T: {}
      [a, b, c, d]
      b < d?
      - T: {}
        [a, b, c, d]
        c < d?
        
        T: {}
        [a, b, c, d]
        
        F: {}
        [a, b, d, c]
      - F: {}
        [a, d, c, b]
        c < b?
        
        T: {}
        [a, d, c, b]
        
        F: {}
        [a, d, b, c]
    - F: {cabd,cadb}
      [a, b, c, d]
      b < d?
      - T: {cabd}
        [a, b, c, d]
        c < d?
        
        T: {cabd}

[a, b, c, d]

F: {cabd}
[a, b, d, c]

F: {cadb}
[a, d, c, b]
c < d?

T: {cadb}
[a, d, c, b]
F: {cadb}
[a, d, b, c]

F: {cabd,cadb}
[d, b, c, a]
b < c?

T: {}
[d, b, c, a]
b < a?
- T: {}
  [d, b, c, a]
  c < a?
  - T: {}
    [d, b, c, a]
  - F: {}
    [d, b, a, c]
- F: {}
  [d, a, c, b]
  c < b?
  - T: {}
    [d, a, c, b]
  - F: {}
    [d, a, b, c]
F: {cabd,cadb}
[d, b, c, a]
b < a?
- T: {}
  [d, b, c, a]
  c < a?
  - T: {}
    [d, b, c, a]
  - F: {}
    [d, b, a, c]
- F: {cabd,cadb}
  [d, a, c, b]
  c < b?
  - T: {cabd,cadb}
    [d, a, c, b]
  - F: {cabd,cadb}
    [d, a, b, c]

F: {bacd,badc,bcad,bcda,bdac,bdca,cbad,cbda,cdba,dbac,dbca,dcba}
usw.

Aufgabe 2

(a) Welcher "Pfad" des Entscheidungsbaumes gehört zu der Liste [1, 7, 5, 2] ?

(b) Überzeuge dich davon, dass hier tatsächlich der Algorithmus selectionsort ausgeführt wird. Woran kann man das z.B. erkennen?

(c) Der Algorithmus selectionsort führt immer - unabhängig von den vorgegebenen Listenelementen - 6 Vergleiche aus. Wie zeigt sich das im Entscheidungsbaum?

(d) Der Algorithmus selectionsort führt eine Reihe unnötiger Vergleiche aus. Gib Beispiele hierfür an.

Ein optimaler Entscheidungsbaum

Wenn ein Sortieralgorithmus die Sortierung nur über Vergleiche von Listenelementen erzeugt, dann lässt sich die Ausführung des Algorithmus bei beliebigen Ausgangslisten über einen Entscheidungsbaum darstellen. Die Tiefe des Baumes (erkennbar an den Einrückungen) zeigt dabei, wie viele Entscheidungen im ungünstigsten Fall auszuführen sind. Im Fall des Algorithmus selectionsort beträgt die Tiefe des Baumes 6.

Am Entscheidungsbaum zeigt sich also, wie gut oder schlecht ein Algorithmus ist. Wenn die Tiefe des Entscheidungsbaums groß bzw. klein ist, dann ist das worst-case-Verhalten des Algorithmus schlecht bzw. gut.

Am Entscheidungsbaum kann auch aufgezeigt werden, wie gut das worst-case-Verhalten eines Sortieralgorithmus überhaupt sein kann: Bei 24 möglichen Anordnungen benötigt man mindestens einen Entscheidungsbaum der Tiefe 5, um alle Anordnungen durch Entscheidungen erzeugen zu können. Das sieht man so ein: Durch 1 Entscheidung erhält man eine Aufteilung der Anordnungen in 2 Teilmengen, durch 2, 3, 4, 5, ... Entscheidungen in 4, 8, 16, 32, ... Teilmengen. Um alle 24 Anordnungen mittels Entscheidungen auseinander zu bekommen, sind daher mindestens 5 Entscheidungen im Entscheidungsbaum erforderlich. Das folgende Baumdiagramm zeigt, wie man mit 5 geschachtelten Entscheidungen tatsächlich alle Anordnungen erhält.

Klicke auf die hell markierten Bedingungen, um den jeweiligen Unterbaum zu öffnen. Du kannst den Baum auch ganz öffnen bzw. schließen.

{abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca,
          cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcba}

a < b?

T: {abcd,abdc,acbd,acdb,adbc,adcb,cabd,cadb,cdab,dabc,dacb,dcab}
c < d?
- T: {abcd,acbd,acdb,cabd,cadb,cdab}
  a < c?
  - T: {abcd,acbd,acdb}
    b < c?
    - T: {abcd}
    - F: {acbd,acdb}
      b < d?
      - T: {acbd}
      - F: {acdb}
  - F: {cabd,cadb,cdab}
    b < d?
    - T: {cabd}
    - F: {cadb,cdab}
      a < d?
      - T: {cadb}
      - F: {cdab}
- F: {abdc,adbc,adcb,dabc,dacb,dcab}
  a < d?
  - T: {abdc,adbc,adcb}
    b < d?
    - T: {abdc}
    - F: {adbc,adcb}
      b < c?
      - T: {abdc}
      - F: {adcb}
  - F: {dabc,dacb,dcab}
    b < c?
    - T: {dabc}
    - F: {dacb,dcab}
      a < c?
      - T: {dacb}
      - F: {dcab}
F: {bacd,badc,bcad,bcda,bdac,bdca,cbad,cbda,cdba,dbac,dbca,dcba}
c < d?
- T: {bacd,bcad,bcda,cbad,cbda,cdba}
  b < c?
  - T: {bacd,bcad,bcda}
    a < c?
    - T: {bacd}
    - F: {bcad,bcda}
      a < d?
      - T: {bcad}
      - F: {bcda}
  - F: {cbad,cbda,cdba}
    a < d?
    - T: {cbad}
    - F: {cbda,cdba}
      b < d?
      - T: {cbda}
      - F: {cdba}
- F: {badc,bdac,bdca,dbac,dbca,dcba}
  b < d?
  - T: {badc,bdac,bdca}
    a < d?
    - T: {badc}
    - F: {bdac,bdca}
      a < c?
      - T: {bdac}
      - F: {bdca}
  - F: {dbac,dbca,dcba}
    a < c?
    - T: {dbac}
    - F: {dbca,dcba}
      b < c?
      - T: {dbca}
      - F: {dcba}