Die Zyklomatische Komplexität des BubbleSort-Algorithmus
https://bildung.social/@oerinformatik/
https://oer-informatik.de/zyklomatische-komplexitaet-bubblesort
Zyklomatische Komplexität, McCabe-Zahl, Bubblesort, Kontrollflussgraph, UML-Aktivitätsdiagramm, Basispfade, Softwaremetriken
tl/dr; (ca. 8 min Lesezeit): Für Bubblesort wird auf vier verschiedene Arten die zyklomatische Komplexität bestimmt. Hintergründe zur Zyklomatischen Komplexität finden sich im Artikel zur Zyklomatischen Komplexität [AI-Assisted]. (Zuletzt geändert am 23.10.2026)
Dieser Artikel ist Teil einer Artikelreihe über die Komplexität von Algorithmen: Laufzeitkomplexität und Big-O-Notation / Zyklomatische Komplexität (McCabe-Zahl) / Zyklomatische Komplexität von Bubblesort
Schon fit in diesem Thema? Nutze die Kann-Liste und die Leitfragen unter dem Artikel als Checkliste, ob Du die relevanten Kompetenzen bereits hast.
Dieser Artikel baut auf der Kann-Liste des Artikels Zyklomatische Komplexität auf.
Als Softwarequalität-Grundlagen kann ich nach Durchlesen des Artikels…
… aus dem Quelltext eines Algorithmus mit verschachtelten Zählschleifen einen Kontrollflussgraphen erstellen und dabei Initialisierung, Vergleich und Inkrement der
for-Schleife an der richtigen Stelle darstellen.… Knoten und Kanten eines UML-Aktivitätsdiagramms zählen und daraus die Zyklomatische Komplexität berechnen.
… die Zyklomatische Komplexität von Bubblesort über Knoten und Kanten, über binäre Verzweigungen und über linear unabhängige Pfade bestimmen.
… begründen, warum unterschiedlich stark zusammengefasste Kontrollflussgraphen dieselbe Zyklomatische Komplexität ergeben.
Darüber hinaus kann ich als Softwarequalität-Expertenwissen…
- … beurteilen, welches Bestimmungsverfahren sich für komplexere Methoden am besten eignet.
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 (2), (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.
Leitfragen
- Warum musst Du eine
for-Schleife im Kontrollflussgraphen in mehrere Teile zerlegen?
Im Schleifenkopf stecken drei Anweisungen, die zu verschiedenen Zeitpunkten ausgeführt werden: die Initialisierung einmal vor der Schleife, der Vergleich vor jedem Durchlauf und das Inkrement am Ende jedes Durchlaufs, siehe Abschnitt „Entwicklung des Kontrollfluss-Graphen“.
- Wie berechnest Du die Zyklomatische Komplexität von Bubblesort aus Knoten und Kanten?
Mit M = e - n + 2: Der zusammengefasste Kontrollflussgraph hat 7 Knoten und 9 Kanten (ohne Start und Stop), also M = 9 - 7 + 2 = 4. Das Aktivitätsdiagramm mit 13 Knoten und 15 Kanten ergibt ebenfalls 4, siehe Abschnitt „Herleitung über Knoten und Kanten des Kontrollflusses von Bubblesort“.
- Welche binären Verzweigungen hat Bubblesort?
Die Bedingungen der äußeren und der inneren Schleife sowie die Vergleichsbedingung mein_array[j] > mein_array[j + 1] – im Kontrollflussgraphen die Knoten (2), (4) und (5). Mit M = b + 1 = 3 + 1 = 4, siehe Abschnitt „Herleitung über die binären Verzweigungen von Bubblesort“.
- Welche vier linear unabhängigen Pfade gibt es durch Bubblesort?
Ein Pfad ohne Durchlauf der äußeren Schleife, einer mit Rücksprung aus der inneren zur äußeren Schleife, einer mit innerem Durchlauf ohne Vertauschung und einer mit Vertauschung. Jeder Pfad wird nur bis zum ersten wiederholten Knoten verfolgt, siehe Abschnitt „Herleitung über die linear unabhängigen Pfade von Bubblesort“.
- Welches Verfahren eignet sich am besten, um die Zyklomatische Komplexität zu bestimmen?
Am eingängigsten ist das Zählen der binären Verzweigungen. Nur Mehrfachverzweigungen wie switch/case muss man vorher umrechnen. Das Ermitteln aller Pfade wird bei größeren Methoden schnell unübersichtlich, siehe Abschnitt „Fazit“.
Links und weitere Informationen
Hinweis zur Nachnutzung als Open Educational Resource (OER)
Dieser Artikel und seine Texte, Bilder, Grafiken, Code und sonstiger Inhalt sind - sofern nicht anders angegeben - lizenziert unter CC BY 4.0. Nennung gemäß TULLU-Regel bitte wie folgt: “Die Zyklomatische Komplexität des BubbleSort-Algorithmus” von oer-informatik.de (H. Stein), Lizenz: CC BY 4.0. Der Artikel wurde unter https://oer-informatik.de/zyklomatische-komplexitaet-bubblesort veröffentlicht, die Quelltexte sind in weiterverarbeitbarer Form verfügbar im Repository unter https://gitlab.com/oer-informatik/algorithmik/pseudocode. Erstellt mit KI-Assistenz; von mir umfassend redaktionell überarbeitet, geprüft und freigegeben. Stand: 23.10.2026.
[Kommentare zum Artikel lesen, schreiben] / [Artikel teilen] / [gitlab-Issue zum Artikel schreiben]
