Interaktive Demo
Bubblesort-Visualisierung
Bubblesort läuft immer wieder durch das Array und tauscht jedes Nachbarpaar, das in falscher Reihenfolge steht. Er ist einfach, mit O(n²) Schritten aber einer der langsamsten Sortieralgorithmen.
Wähle „Sortiert“ als Ausgangsreihenfolge: Ein einziger Durchlauf ohne Tausch genügt. „Umgekehrt“ ist der schlechteste Fall.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Unsortiertes Element
- Verglichene Nachbarn
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n)
Schon sortiert: Ein Durchlauf ohne einen einzigen Tausch beendet die Sortierung.
Mittlerer Fall
O(n²)
Jedes Element rückt pro Tausch nur eine Stelle weiter, das braucht etwa n²/2 Vergleiche.
Schlechtester Fall
O(n²)
Umgekehrte Reihenfolge: Jeder Durchlauf muss jedes verglichene Paar tauschen.
Zusätzlicher Speicher
O(1)
Es werden nur Nachbarn getauscht, zusätzlicher Speicher ist nicht nötig.
Stabil
Ja
Gleiche Nachbarn werden nie getauscht.
In-place
Ja
Elemente werden nur innerhalb des Arrays getauscht.
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.
Im Vergleich mit den anderen Sortieralgorithmen
| Algorithmus | Bester Fall | Mittlerer Fall | Schlechtester Fall | Zusätzlicher Speicher | Stabil | In-place |
|---|---|---|---|---|---|---|
| Bubblesort diese Seite | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Selectionsort | O(n²) | O(n²) | O(n²) | O(1) | Nein | Ja |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Shellsort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | Nein | Ja |
| Treesort | O(n log n) | O(n log n) | O(n²) | O(n) | Ja | Nein |
| Tournamentsort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Patiencesort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Blocksort | O(n) | O(n log n) | O(n log n) | O(1) | Ja | Ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein | Ja |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
1. Nachbarn vergleichen
Ein Durchlauf vergleicht jedes Element mit seinem rechten Nachbarn. Ist das linke größer, werden die beiden getauscht.
2. Das Größte steigt auf
Das größte Element wird immer weiter getauscht, bis es am Ende des Arrays ankommt, wie eine aufsteigende Blase im Wasser. Nach jedem Durchlauf ist der unsortierte Teil ein Element kürzer.
3. Früh aufhören
Kommt ein ganzer Durchlauf ohne einen einzigen Tausch aus, ist alles in Reihenfolge und die Sortierung kann enden. Das macht Bubblesort bei schon sortierten Arrays schnell.