Die Zyklomatische Komplexität des BubbleSort-Algorithmus

https://oer-informatik.de/zyklomatische-komplexitaet-bubblesort

tl/dr; (ca. 3 min Lesezeit): Für Bubblesort wird auf vier verschiedene Arten die zyklomatische Komplexität bestimmt. Hintergründe zur Zyklomatischen Komplexität finden sich in diesem Artikel.

Am Beispiel des Bubblesort-Algorithmus soll die Zyklomatische Komplexität dargestellt werden.

Der Algorithmus lässt sich in einem Java-Programm etwa so umsetzen:

public static int[] bubblesort(int[] mein_array) {
     int temp;
     for (int i = 1; i < mein_array.length; i++) {
         for (int j = 0; j < mein_array.length - i; j++) {
             if (mein_array[j] > mein_array[j + 1]) {
                 temp = mein_array[j];
                 mein_array[j] = mein_array[j + 1];
                 mein_array[j + 1] = temp;
             }
         }
     }
     return mein_array;
 }

Entwicklung des Kontrollfluss-Graphen

Zur Berechnung der Zyklomatischen Komplexität wird die Anzahl der Knoten und Kanten benötigt. Aufgepasst werden muss insbesondere bei den zählergesteuerten Schleifen (for(...)), da sich hier drei Statements verstecken, die zu unterschiedlichen Zeitpunkten im Kontrollfluss ausgeführt werden: Die Initialisierung (int i=1) zu Beginn des Eintritts in die Schleife, die Inkrementierung (i++) am Ende jedes Durchlaufs und der Vergleich (i<mein_array.length) vor jedem Durchlauf.

Herleitung über Knoten und Kanten aus dem UML-Aktivitätsdiagramm

Der Kontrollfluss lässt sich aus dem UML-Aktivitätsdiagramm herleiten. Für Bubblesort sieht das Aktivitätsdiagramm folgendermaßen aus:

Das Aktivitätsdiagramm stellt eine besondere Art des Kontrollflussgraphen dar - wir zählen hier 13 Knoten (Aktivitäten und Entscheidungsknoten, Start und Ende nicht eingerechnet) sowie 15 Kanten (ohne die Kanten an Start und Stop). Bereits daraus lässt sich die Zyklomatische Komplexität errechnen:

M = e - n + 2 = 15 - 13 + 2 = 4

Herleitung über Knoten und Kanten des Kontrollflusses von Bubblesort

Wenn wir aus dem Aktivitätsdiagramm alle Sequenzen (unverzweigte aufeinanderfolgende Operationen) und die Entscheidungsknoten mit den vorigen Knoten zusammenfassen, erhalten wir einen einfachen Kontrollflussgraphen:

Durch die Vereinfachungen variieren die Anzahl der Knoten und Kanten, aber das Ergebnis bleibt:

M = e - n + 2 = 9 - 7 + 2 = 4

Herleitung über die binären Verzweigungen von Bubblesort

Der Kontrollfluss weist 3 binäre Verzweigungen auf: die Knoten (3), (4) und (5). Die alternativen Zweige sind oben jeweils farblich hervorgehoben. Auch mit dieser Berechnung können wir die _Zyklomatische Komplexität bestimmen.

M = b + 1 = 3 + 1 = 4

Herleitung über die linear unabhängigen Pfade von Bubblesort

Alternativ ließen sich schließlich noch die linear unabhängigen Pfade bestimmen. Die Pfade werden jeweils durchlaufen, bis ein Knoten erreicht wird, der in dem jeweiligen Pfad bereits erreicht wurde.

Pfad 1: Start->1->2->7->Stop

Pfad 2: Start->1->2->3->4-> (wiederholt 2)

Pfad 3: Start->1->2->3->4->5-> (wiederholt 4)

Pfad 4: Start->1->2->3->4->5->6-> (wiederholt 4)

Wie erwartet finden sich vier linear unabhängige Pfade. Es wird aber bereits deutlich, dass dieser Weg bei komplexeren Methoden der am wenigsten geeignete ist, um die Zyklomatische Komplexität zu bestimmen.

Herleitung aus dem Quelltext

Auch direkt aus dem Quelltext lassen sich Knoten und Kanten ermitteln. Hilfreich ist es, hierbei mit Farben und Markierungen für die bedingten Anweisungen zu arbeiten:

Es ergeben sich aus dem so ermittelten Kontrollflussgraphen 7 Knoten und 9 Kanten (exklusive Start- und Endknoten).

M = e - n + 2 = 9 - 7 + 2 = 4

Fazit

Das eingängigste Verfahren zur Bestimmung der Zyklomatischen Komplexität ist die Bestimmung der binären Verzweigungen. Lediglich bei Verzweigungen mit mehreren Alternativen (z.B. switch/case-Konstrukte) kann das Umwandeln in binäre Verzweigungen fehlerträchtig sein.

Quellen und offene Ressourcen (OER)

Die Ursprungstexte (als Markdown), Grafiken und zugrunde liegende Diagrammquelltexte finden sich (soweit möglich in weiterbearbeitbarer Form) in folgendem git-Repository:

https://gitlab.com/oer-informatik/algorithmik/pseudocode.

Sofern nicht explizit anderweitig angegeben sind sie zur Nutzung als Open Education Resource (OER) unter Namensnennung (H. Stein, oer-informatik.de) freigegeben gemäß der Creative Commons Namensnennung 4.0 International Lizenz (CC BY 4.0).