/ Algorithmen & Komplexität

Bubble Sort Vergleiche

Anzahl Vergleiche im Worst Case beim Bubble Sort: Vergleiche = n · (n − 1) / 2. Wächst quadratisch mit n.

01 · Eingabe

Bubble Sort Vergleiche berechnen

Anzahl Vergleiche im Worst Case beim Bubble Sort: Vergleiche = n · (n − 1) / 2. Wächst quadratisch mit n.

Lösen für

Vergleiche = n · (n − 1) / 2

n Elementanzahl

Worum geht es?

Bubble Sort vergleicht in jeder von n − 1 Durchläufen benachbarte Paare und tauscht sie bei Bedarf. Im Worst Case (komplett umgekehrt sortierte Eingabe) entstehen genau n · (n − 1) / 2 Vergleiche.

Die Formel entspricht der Anzahl ungeordneter Paare in einem Array der Länge n — also der Summe 1 + 2 + … + (n − 1).

Fall	Vergleiche	Tausche
Best Case	n − 1	0
Average	≈ n² / 2	≈ n² / 4
Worst Case	n · (n − 1) / 2	n · (n − 1) / 2

Die Formel

Formel Bubble Sort

Vergleiche = n · (n − 1) / 2

Umstellung:
    n = (1 + √(1 + 8 · Vergleiche)) / 2

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
n	Elementanzahl	—	Anzahl zu sortierender Elemente.
Vergleiche	Vergleiche	—	Anzahl Vergleiche im Worst Case.

Minimal-Beispiel

n = 10 Elemente, vollständig umgekehrt sortiert:

Rechnung Worst Case

Vergleiche = 10 · 9 / 2
           = 45

Praxis-Beispiele

Beispiel 1 — 1000 Elemente

Rechnung n = 1000

Vergleiche = 1000 · 999 / 2
           = 499 500

Beispiel 2 — n aus Vergleichszahl rekonstruieren

Profiler meldet 4950 Vergleiche:

Rechnung Rückrechnung

n = (1 + √(1 + 8 · 4950)) / 2
  = (1 + √39 601) / 2
  = (1 + 199) / 2
  = 100

Beispiel 3 — Vergleich zu Merge Sort

n = 100 000:

Rechnung Vergleich

Bubble:  100 000 · 99 999 / 2 ≈ 5 · 10⁹
Merge:   100 000 · log₂(100 000) ≈ 1,7 · 10⁶

Faktor: ca. 3000-fach.