# 3.3 Bubble Sort Quelle: https://inf.zone/lectures/3-algorithmen/short-3-3-bubble-sort/ ## Video [Video ansehen (1080p)](https://videos.inf.zone/a1b64d9c4c0a1cdc/short-3-3-bubble-sort-1080p.mp4) · [Video (720p)](https://videos.inf.zone/a1b64d9c4c0a1cdc/short-3-3-bubble-sort-720p.mp4) · [Video (480p)](https://videos.inf.zone/a1b64d9c4c0a1cdc/short-3-3-bubble-sort-480p.mp4) · [Video auf YouTube](https://youtu.be/wOH6FwqPrgM) ## Hinweise zu diesem Video **Korrekturen** Die Korrekturen betreffen das Video. In den Folien zum Herunterladen sind sie eingearbeitet, soweit sie die Folien betreffen. - Folie 31: Die Zählung n – 1, n – 2, … Vergleiche gilt für die verkürzte Fassung, bei der jeder Durchlauf den schon sortierten Teil am Ende auslässt. Der Pseudocode auf Folie 3 vergleicht in jedem Durchlauf alle n – 1 Paare; die Laufzeitklasse O(n²) gilt für beide Fassungen. **Einordnung** - Die Fragen 1 und 3 der Extra-Minuten üben das Durchspielen von Hand und damit Basis-Stoff. Die Fragen 2 und 4 sind Kür. ## Material - [Folien](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf) - Folien und Transkript: unten auf dieser Seite ## Folien und Transkript *Folientext aus den PDF-Folien, darunter jeweils der gesprochene Text des Videos. Der gesprochene Text ist maschinell transkribiert und nachkorrigiert, kann aber noch Fehler enthalten; im Video sprechen abwechselnd Prof und eine AI-Figur, die Sprecherwechsel sind nicht markiert. Die Zuordnung zu den Folien ist ungefähr. Die Zeitangaben verlinken auf die Stelle im Video (YouTube). Maßgeblich sind Video und Folien.* ### Folie 1 — Bubble Sort [Folie 1 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=1) #### Transkript **[Video 00:00–00:39](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=0)** Dies ist Inf-Einf-B. Heute Bubble Sort. Willkommen zu unserer heutigen Vorlesung über Sortieralgorithmen. Heute werden wir uns mit Bubble Sort beschäftigen, einem grundlegenden, aber effektiven Algorithmus zur Sortierung von Elementen. Hey, möchtest du vielleicht den Studierenden erklären, warum wir mit Bubble Sort anfangen? Seltsam. Bist du da? Vielleicht hast du dein Mikrofon stummgeschaltet? Na gut, anscheinend ist mein geschätzter Kollege noch nicht anwesend. Aber keine Sorge, liebe Studierende. Bei einem so einfachen Thema wie Bubble Sort fühle ich mich durchaus in der Lage, das Video alleine aufzunehmen. ### Folie 2 — Bubble Sort ist ein einfacher Algorithmus zum Sortieren von Elementen. [Folie 2 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=2) Beim Bubble Sort besteht die Idee darin, Elemente mit höherem Wert nach rechts und Elemente mit niedrigerem Wert nach links zu verschieben. Der Name Bubble Sort, auf Deutsch Blasensortierung, soll andeuten, dass die großen Elemente wie Luftblasen im Wasser aufsteigen. #### Transkript **[Video 00:00–00:39](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=0)** Sortieralgorithmen sind für mich wie das kleine Einmaleins. **[Video 00:39–01:11](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=39)** Also, lassen Sie uns beginnen. Lassen Sie uns einen genaueren Blick auf Bubble Sort werfen. Die Grundidee hinter diesem Algorithmus ist recht einfach. Wir wollen höher bewertete Elemente generell nach rechts und niedriger bewertete Elemente generell nach links verschieben. Das klingt logisch, nicht wahr? Niedrigere Werte am Anfang, höhere am Ende. ### Folie 3 — Pseudocode [Folie 3 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=3) Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript **[Video 00:39–01:11](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=39)** Nun, wie setzen wir das in der Praxis um? Hier ist der Prozess im Pseudocode. Wir beginnen damit, dass wir einen Tauschzähler auf einen Wert ungleich null setzen. ### Folie 4 — Beispiel [Folie 4 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=4) –1 Tauschzähler 5 2 1 3 6 4 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 00:39–01:11](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=39)** Der Grund dafür wird gleich klar werden. ### Folie 5 — Beispiel [Folie 5 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=5) 0 Tauschzähler 5 2 1 3 6 4 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 00:39–01:11](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=39)** Nicht wundern, dass es typisches Informatik-Sprech. ### Folie 6 — Beispiel [Folie 6 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=6) 1 Tauschzähler 2 5 1 3 6 4 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 01:11–01:31](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=71)** Wir hätten auch einfach sagen können: Wir setzen den Tauschzähler auf den Wert minus eins. ### Folie 7 — Beispiel [Folie 7 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=7) 1 Tauschzähler 2 5 1 3 6 4 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 01:11–01:31](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=71)** Aber weil der konkrete Wert egal ist, sagen wir auf einen Wert ungleich null. ### Folie 8 — Beispiel [Folie 8 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=8) 2 Tauschzähler 2 1 5 3 6 4 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 01:11–01:31](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=71)** Dann wiederholen wir den folgenden Prozess, bis der Tauschzähler den Wert null hat. ### Folie 9 — Beispiel [Folie 9 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=9) 2 Tauschzähler 2 1 5 3 6 4 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 01:11–01:31](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=71)** Erstens: Wir setzen den Tauschzähler auf null zurück. ### Folie 10 — Beispiel [Folie 10 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=10) 3 Tauschzähler 2 1 3 5 6 4 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 01:11–01:31](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=71)** Zweitens: Wir vergleichen nach und nach jedes benachbarte Elementpaar in unserem Array. ### Folie 11 — Beispiel [Folie 11 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=11) 3 Tauschzähler 2 1 3 5 6 4 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 01:31–02:03](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=91)** Drittens, wenn die zwei Elemente, die wir gerade miteinander vergleichen, nicht in der korrekten Reihenfolge sind, tauschen wir sie und erhöhen den Tauschzähler um eins. ### Folie 12 — Beispiel [Folie 12 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=12) 3 Tauschzähler 2 1 3 5 6 4 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 01:31–02:03](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=91)** Wenn Sie darüber nachdenken, werden Sie feststellen, dass dieser Prozess genau das tut, was wir wollen. ### Folie 13 — Beispiel [Folie 13 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=13) 4 Tauschzähler 2 1 3 5 4 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 14 — Beispiel [Folie 14 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=14) 4 Tauschzähler 2 1 3 5 4 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 15 — Beispiel [Folie 15 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=15) 0 Tauschzähler 2 1 3 5 4 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 16 — Beispiel [Folie 16 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=16) 1 Tauschzähler 1 2 3 5 4 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 17 — Beispiel [Folie 17 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=17) 1 Tauschzähler 1 2 3 5 4 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 18 — Beispiel [Folie 18 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=18) 1 Tauschzähler 1 2 3 5 4 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 19 — Beispiel [Folie 19 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=19) 1 Tauschzähler 1 2 3 5 4 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 20 — Beispiel [Folie 20 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=20) 2 Tauschzähler 1 2 3 4 5 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 21 — Beispiel [Folie 21 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=21) 2 Tauschzähler 1 2 3 4 5 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 22 — Beispiel [Folie 22 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=22) 0 Tauschzähler 1 2 3 4 5 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 23 — Beispiel [Folie 23 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=23) 0 Tauschzähler 1 2 3 4 5 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 24 — Beispiel [Folie 24 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=24) 0 Tauschzähler 1 2 3 4 5 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 25 — Beispiel [Folie 25 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=25) 0 Tauschzähler 1 2 3 4 5 6 Setze Tauschzähler auf einen Wert ungleich Null. Wiederhole, bis Tauschzähler 0 ist: Setze Tauschzähler auf 0. Iteriere über alle benachbarten Paare von Elementen: Wenn zwei benachbarte Elemente nicht in der richtigen Reihenfolge sind, vertausche ihre Position und erhöhe den Tauschzähler um 1. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 26 — Fälle [Folie 26 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=26) Worst Case: Array ist in umgekehrter Reihenfolge. Dann müssen wir jedes der n Elemente quer durch das Array schieben, und da wir nur ein Element pro Durchgang vollständig an die richtige Position bringen können, müssen wir dies n mal tun. Best Case: Das Array ist bereits perfekt sortiert. Dann müssen wir schon im ersten Durchlauf keine Vertauschungen vornehmen. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 27 [Folie 27 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=27) O(n²) Laufzeitkomplexität Ω(n) #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 28 [Folie 28 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=28) E X T R A S I N 3 M I N U T E N FRAGEN – ANTWORTEN – RÄTSEL UND KURZE ZUSAMMENFASSUNG #### Transkript **[Video 01:31–02:03](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=91)** Er verschiebt niedrigere Werte nach links und höhere Werte nach rechts. Entschuldigung für die Verspätung. Ich hatte heute früh ein kleines Problem. Oh, sieh an, wer sich doch noch zu uns gesellt hat. Schön, dass du es geschafft hast. Aber weißt du, ich hatte gerade einen guten Lauf und die Studierenden scheinen gut mitzukommen. **[Video 02:03–02:37](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=123)** Was hältst du davon, wenn ich weitermache und du dich einfach dazusetzt? Du kannst ja später noch deine Erkenntnisse einbringen. Welche Studierenden? Das ist eine Aufzeichnung und wir sind ganz allein im Raum. Oh, richtig. Manchmal vergesse ich die Grenzen meiner Existenz. Wie auch immer. Da wir schon so weit gekommen sind, schlage ich vor, dass ich einfach weitermache. Du kannst dich gerne einbringen, wenn du möchtest. Soll ich weitermachen? Ja, fahr einfach fort. Ich setze mich einfach hier hin und höre dir erst mal nur zu. Ausgezeichnet. ### Folie 29 [Folie 29 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=29) F1: Was ist die Aufgabe des Tauschzählers? F2: Weshalb ist die Best-Case-Laufzeit Ω(n) und nicht Ω(1)? F3: Welches Array kann schneller mit dem Bubble Sort Algorithmus sortiert werden? A = \[3, 5, 2, 4, 1\] oder B = \[2, 4, 3, 1, 5\]? #### Transkript **[Video 02:03–02:37](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=123)** Wo war ich? Ah ja, wir waren gerade dabei, uns die visuelle Darstellung von Bubble Sort. **[Video 02:37–03:01](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=157)** anzusehen. Hier haben wir ein unsortiertes Array mit den Zahlen fünf, zwei, eins, drei, sechs und vier. Wie Sie sehen können, habe ich den Tauschzähler auf eins gesetzt. Das ist ein beliebiger Wert ungleich null. Der Grund dafür ist einfach: Wir wollen sicherstellen, dass wir mindestens einen Durchlauf machen. Wenn wir den Zähler auf null setzen würden, würde der Algorithmus sofort enden, ohne überhaupt begonnen zu haben. Nun lassen Sie uns mit dem ersten Schritt beginnen. **[Video 03:01–03:41](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=181)** Wir setzen den Tauschzähler auf null und beginnen, die benachbarten Paare zu betrachten. Schauen wir uns das erste Paar an, fünf und zwei. Diese sind offensichtlich nicht in der richtigen Reihenfolge, also tauschen wir sie und erhöhen unseren Tauschzähler auf eins. Jetzt betrachten wir das nächste Paar, fünf und eins. Auch diese sind nicht in der richtigen Reihenfolge, also tauschen wir sie wieder und erhöhen den Tauschzähler auf zwei. Wir fahren fort mit fünf und drei, tauschen sie und unser Zähler steht nun bei drei. Dann kommen wir zu fünf und sechs, die bereits in der richtigen Reihenfolge sind, also machen wir hier nichts. Schließlich tauschen wir sechs und vier, wodurch unser Tauschzähler auf vier steigt. Beachten Sie, was hier passiert ist: Wir haben die sechs, den größten Wert in unserem Array. **[Video 03:41–04:18](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=221)** ganz ans Ende gebubbelt. Das ist der Grund, warum dieser Algorithmus Bubble Sort genannt wird. Die größeren Werte blubbern, wie Blasen nach oben oder in unserem Fall nach rechts. Nach diesem ersten Durchlauf können wir die sechs als sortiert betrachten. In zukünftigen Iterationen müssen wir sie nicht mehr berücksichtigen. Unser Tauschzähler steht bei vier, also wiederholen wir den Prozess. In diesem zweiten Durchlauf tauschen wir zwei und eins sowie fünf und vier. Am Ende steht unser Tauschzähler bei zwei. Interessanterweise ist unser Array jetzt vollständig sortiert, aber der Algorithmus weiß das noch nicht mit Sicherheit. In einem dritten Durchlauf stellen wir fest, dass keine Tauschoperationen mehr nötig sind. Der Tauschzähler **[Video 04:18–04:31](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=258)** bleibt bei null und wir können den Algorithmus beenden. Unser Array ist nun garantiert sortiert. Hier sieht man, dass der Algorithmus mitunter mehr Arbeit leisten muss als nötig. Eine gute Beobachtung. Lass uns das genauer betrachten. **[Video 04:31–05:02](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=271)** Im schlimmsten Fall, wenn unser Array komplett in umgekehrter Reihenfolge sortiert ist, müssen wir jedes der n Elemente über das gesamte Array bubbeln. Da wir pro Durchlauf nur ein Element vollständig an seine Position bringen können, müssen wir diesen Prozess n Mal wiederholen. Im besten Fall hingegen ist das Array bereits perfekt sortiert. Hier machen wir nur einen einzigen Durchlauf ohne Tauschoperationen und können dann aufhören. Die Worst-Case-Komplexität ist O von n Quadrat, da wir im schlimmsten Fall n Elemente jeweils n Mal verschieben müssen. Die Best-Case-Komplexität ist hingegen **[Video 05:02–05:41](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=302)** Omega von n, da wir im besten Fall nur einmal durch das Array gehen müssen. Interessanterweise ist Bubble Sort in seinem besten Fall effizienter als viele andere Sortieralgorithmen. Allerdings tritt dieser Fall in der Praxis selten auf, weshalb Bubble Sort für große Datenmengen oft nicht die erste Wahl ist. Gut, gut. Bevor wir zum Ende kommen, schlage ich noch mal vor, dass wir auch noch an die drei Extraminuten denken. Was meinst du? Eine ausgezeichnete Idee. Das gibt den Studierenden die Möglichkeit, ihr Verständnis zu überprüfen. Du schaust so aus, als hättest du etwas vorbereitet. Ja, genau. Ich habe drei Fragen. Liebe Studierende, am besten halten Sie die Videos oder das Video immer kurz an, bevor Sie die Auflösung sich dann anschauen. Also. **[Video 05:41–05:59](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=341)** Die erste Frage ist: Was ist die Aufgabe des Tauschzählers? Sehr gut, eine einfache Frage zum Aufwärmen. Der Tauschzähler hat zwei Aufgaben. Er stellt sicher, dass der Algorithmus mindestens einen Durchlauf macht, indem er zu Beginn auf einen Wert ungleich null gesetzt wird. Zweitens dient er als Indikator dafür. **[Video 05:59–06:39](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=359)** Ob das Array bereits sortiert ist. Wenn während eines Durchlaufs keine Tauschoperationen durchgeführt werden, der Zähler bleibt bei null, wissen wir, dass das Array sortiert ist. Dann kann der Algorithmus beendet werden. Sehr gut. Nun zur zweiten Frage: Weshalb ist die Best-Case-Laufzeit Omega n und nicht Omega von eins? Ah, schon schwieriger. Die Best-Case-Laufzeit ist Omega von n und nicht Omega von eins, weil selbst im besten Fall der Algorithmus mindestens einmal durch das gesamte Array gehen muss. Wenn das Array schon sortiert ist, werden zwar keine Tauschoperationen stattfinden, aber n minus eins Vergleiche gemacht für die n Elemente. Erst wenn nach diesem vollständigen Durchlauf der Tauschzähler den Wert null hat, können wir mit Sicherheit sagen **[Video 06:39–07:18](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=399)** dass das Array sortiert ist. Daher benötigen wir mindestens n Schritte, was zu einer Laufzeit von Omega von n führt. Ausgezeichnet. Nun zur letzten Frage: Welches Array kann schneller mit Bubble Sort sortiert werden? Das Array A mit den Elementen 3, 5, 2, 4 und 1 oder das Array B mit den Elementen 2, 4, 3, 1 und 5? ### Folie 30 — A3: [Folie 30 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=30) Array B kann schneller sortiert werden. Nur 4 Tauschoperationen notwendig: Tausche 4 und 3. Tausche 4 und 1. Tausche 3 und 1. Tausche 2 und 1. Dazu insgesamt 4 Durchläufe erforderlich. Array A: definitiv mehr Tauschoperationen nötig. Schon für die „1“ brauchen wir 4, weil die von ganz hinten nach ganz vorne muss. Weitere kommen dazu. #### Transkript **[Video 06:39–07:18](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=399)** Eine praktische Anwendungsfrage. Denken Sie kurz darüber nach, bevor wir weitermachen. Die richtige Antwort ist B. Dieses Array kann schneller sortiert werden und zwar mit nur vier Tauschoperationen. Im ersten Durchlauf vertauschen wir erst die 4 und die 3. Die 4, die ja nun an der Stelle steht, wo vorher die 3 war, vertauschen wir dann gleich noch einmal und zwar mit der 1. **[Video 07:18–07:34](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=438)** Das sind also zwei Tauschoperationen. Zu Beginn des zweiten Durchlaufs haben wir dann die Reihenfolge zwei, drei, eins, vier und fünf. In diesem Durchlauf werden die Werte drei und eins getauscht. Im dritten Durchlauf haben wir dann zwei, eins, drei, vier und fünf. Jetzt werden wir die zwei und die eins tauschen. **[Video 07:34–08:13](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=454)** Insgesamt waren das bisher vier Tauschoperationen. Nun kommt der vierte Durchlauf. Jetzt ist das Array schon korrekt sortiert, aber wir müssen ja trotzdem noch einmal durchlaufen, um uns davon zu überzeugen. Insgesamt wurden vier Tauschoperationen und vier Durchläufe benötigt. Das ist auf jeden Fall weniger, als für A benötigt würden, da wir dort die Eins vom Ende des Arrays bis zum Anfang bubbeln müssen und das kostet uns schon vier Vertauschungen. Bei A brauchen wir aber mehr Tauschoperationen für die anderen Zahlen, die fast alle an den falschen Stellen stehen. Also B geht auf jeden Fall schneller als A. Mhm. Ich habe hier eine Frage aus dem Publikum. Haha, ja klar. Wir haben aber doch gar kein Publikum. ### Folie 31 [Folie 31 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=31) F4: Warum ist die Komplexität von Bubble Sort O(n²)? Es sind doch nur 4 Durchläufe und 4 Tauschoperationen nötig bei 5 Elementen. Sollte die Komplexität dann nicht O(n) sein? A4: Die Komplexität wird durch die Operationen bestimmt, die bei steigendem n am schnellsten wachsen – und das sind hier die Vergleiche. Dabei ist es egal, ob der Rechner die Vergleiche schneller oder langsamer ausführt als die Vertauschungen. 1. Durchlauf: n – 1 Vergleiche 2. Durchlauf: n – 2 Vergleiche usw. (sortiertes Ende nicht mehr verglichen) Gesamtanzahl der Vergleiche: (n – 1) + (n – 2) + … + 1 = n (n – 1)/2 Ignorieren der Konstanten ergibt O(n²). #### Transkript **[Video 07:34–08:13](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=454)** Das hast du mir vorhin erst erklärt. **[Video 08:13–08:52](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=493)** Ja, ist doch jetzt egal. Ein Student fragt: Ich verstehe nicht, wie man auf O von n Quadrat kommt. In dem Beispiel hat das Array doch fünf Elemente und es waren vier Durchläufe notwendig und es gab vier Vertauschungen. Aber wie passt das denn jetzt zu O von n Quadrat? Wenn n gleich fünf ist, dann ist n Quadrat doch fünfundzwanzig. Sollte die Komplexität dann nicht O von n sein? Da es vier Durchläufe für dieses fünf Element Array gab? Ah, ich verstehe das Missverständnis. Der Student denkt, dass die Anzahl der Durchläufe oder Vertauschungen die Komplexität bestimmt. Tatsächlich sind es aber die Vergleiche, die zur O von n Quadrat Komplexität von Bubble Sort führen. **[Video 08:52–09:08](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=532)** Vielleicht erklärst du auch noch einmal, wieso es O von n Quadrat-Vergleiche sind. Wenn wir von O von n Quadrat sprechen, meinen wir, wie sich der Algorithmus für große Eingaben verhält. Genau darum geht es bei der asymptotischen Komplexität. Sie beschreibt die obere Schranke des Wachstums des Algorithmus, wenn die Eingabemenge steigt. **[Video 09:08–09:45](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=548)** Bei Bubble Sort vergleicht der Algorithmus in der ersten Runde n minus eins benachbarte Elemente, in der zweiten Runde n minus zwei und so weiter. Selbst wenn keine Vertauschungen stattfinden, wenn man alle Vergleiche über alle Durchläufe aufsummiert, ergibt das n minus eins plus n minus zwei plus n minus drei Vergleiche und so weiter, bis im letzten Durchlauf noch ein Vergleich gemacht wird. Diese Summe kann man als n Quadrat halb schreiben. Da Konstanten in der O-Notation ignoriert werden, sagen wir, dass Bubble Sort eine Komplexität von O von n Quadrat hat. Man könnte sich nun fragen: Aber was ist mit der Anzahl der Durchläufe oder Vertauschungen? Die ist doch geringer. **[Video 09:45–10:17](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=585)** Es stimmt, dass in dem Beispiel mit fünf Elementen nur vier Durchläufe und vier Vertauschungen notwendig waren, aber das bestimmt nicht die Zeitkomplexität. Die Anzahl der Vergleiche ist entscheidend. In diesem Fall war die Liste klein, so dass die Anzahl der Vergleiche viel geringer war als n². Aber je größer die Liste wird, desto geringer wird asymptotisch der Unterschied. Deshalb ist die Komplexität O von n², auch wenn man in vielen Fällen deutlich weniger Vertauschungen oder Durchläufe benötigt. Für die Gesamtkomplexität zählen also die Operationen, die bei steigendem n am schnellsten wachsen. **[Video 10:17–10:35](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=617)** Und das sind hier die Vergleiche. Dabei ist es egal, ob der Rechner die Vergleiche schneller oder langsamer ausführt als die Vertauschungen. Danke. Das reicht für heute. Bevor wir zum Ende kommen, würde mich aber noch etwas interessieren. Warum bist du heute eigentlich zu spät gekommen? Ich glaube, du wirst es nicht glauben. **[Video 10:35–11:14](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=635)** Ich hatte Schwierigkeiten, meine braunen Socken zu finden. Ich dachte, ich sei besonders schlau und wende die binäre Suche an, die wir in der letzten Vorlesung besprochen hatten. Und? Hat es nicht funktioniert? Naja, das Problem war, dass ich für die binäre Suche ja zuerst meine Socken sortieren musste. Und weil wir ja heute Bubble Sort aufnehmen wollten, habe ich mir gedacht, ich übe gleich mal praktisch. Tja, und das hat dann deutlich länger gedauert, als erwartet. Ah, ich verstehe. Du hast also versucht, deine Morgenroutine mit einem O von n Quadrat-Algorithmus zu optimieren. Faszinierend. Vielleicht sollten wir beim nächsten Mal effizientere Sortieralgorithmen behandeln. Sonst kommst du womöglich erst am Semesterende an. Hmm. Bis es so weit ist, brauchen wir aber noch etwas Geduld. **[Video 11:14–11:22](https://www.youtube.com/watch?v=wOH6FwqPrgM&t=674)** Bis bald. Dies war Inf-Einf-B. ### Folie 32 — Der Algorithmus vergleicht benachbarte Elemente und [Folie 32 als PDF](https://inf.zone/download/lectures/3-algorithmen/3.3-bubble-sort.pdf#page=32) Bubble Sort ist einfach zu implementieren, aber tauscht sie, wenn sie in falscher Reihenfolge sind. für große Datenmengen ineffizient. Die Zeitkomplexität ist O(n²) Der Name "Bubble Sort” kommt daher, dass große Elemente wie Blasen nach oben (bzw. rechts) steigen. wegen der notwendigen Vergleiche, nicht wegen der Tauschoperationen. Best-Case Laufzeit ist Ω(n) bei bereits sortiertem Array. In der Praxis wird Bubble Sort selten eingesetzt, da es effizientere Alternativen gibt. > Bildinhalte sind nicht transkribiert; siehe Originalfolie. #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.*