Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Bubble Sort Algorithmus [mit Animation, Deutsch]
Das Wichtigste aus dem Video
Transkriptautomatisch erstellt · 52 Zeilen
- In diesem Video zeige ich euch wie Bubble Sort funktioniert und wie man die Zeitkomplexität von Bubble Sort bestimmt.
- Wir wollen diese sieben Zahlen mit Bubble Sort sortieren. Wir vergleichen nun, von links beginnend, jeweils zwei Elemente miteinander und tauschen
- diese, wenn sie nicht in der richtigen Reihenfolge stehen. Wir beginnen mit der 6 und der 2. Diese stehen nicht in der richtigen Reihenfolge, also tauschen
- wir sie. Die 6 und die 4 stehen ebenfalls nicht in der richtigen Reihenfolge und wir tauschen
- auch diese. Die 6 und 9 stehen in der richtigen Reihenfolge zueinander.
- Die 9 und die 3 wieder nicht; wir tauschen sie. Und das gleiche machen wir für die die 9 und die 1 … und die 9 und die 7
- Das größte Element wurde nun bis ganz nach rechts geschoben, und wir teilen das Array links von diesem Element gedanklich in einen linken, nicht sortierten, und einen rechten,
- sortierten Teil. Wir starten erneut am Anfang des Arrays und vergleichen die 2 mit der 4. Diese liegen
- in korrekter Reihenfolge und müssen nicht vertauscht werden. Das gleiche gilt für die 4 und die 6.
- Die 6 und die 3 stehen in umgekehrter Reihenfolge zueinander und müssen vertauscht werden. Das gleiche machen wir für die 6 und die 1.
- Die 6 und die 7 stehen in korrekter Reihenfolge zueinander und müssen nicht getauscht werden. Damit sind wir am Ende des unsortierten Bereichs angekommen und schieben die Trennlinie eine
- Position nach links. Wir starten wieder am Anfang.
- Die 2 und die 4 liegen nach wie vor richtig zueinander. Die 4 und die 3 müssen wir tauschen; ebenso die 4 und die 1.
- Die 4 und die 6 liegen bereits in richtiger Reihenfolge. Wir sind wieder am Ende des unsortierten Bereichs angekommen und schieben die Trennlinie weiter
- nach links. Wir beginnen erneut am Anfang.
- 2 und 3 stehen in korrekter Reihenfolge; 3 und 1 müssen vertauscht werden; und 3 und 4 stehen in korrekter Reihenfolge.
- Wir schieben die Trennlinie weiter nach links … und beginnen erneut am Anfang. 2 und 1 müssen wir tauschen; 2 und 3 stehen korrekt zueinander.
- Wir schieben die Trennlinie ein letztes Mal um eine Position nach links. Die letzten zwei Zahlen des unsortierten Bereichs, die 1 und die 2, stehen bereits in der richtigen
- Reihenfolge zueinander. Und damit sind alle Zahlen sortiert und der Bubble-Sort-Algorithmus beendet.
- Wenn wir die Zahlen als Balken darstellen und den Sortiervorgang in Zeitraffer abspielen, dann steigen die Elemente nach und nach zu ihren Zielpositionen auf − ähnlich wie
- Luftblasen − englisch „bubbles“. Daher der Name „Bubble Sort“. Kommen wir zur Zeitkomplexität von Bubble Sort.
- Die Anzahl der zu sortierenden Elemente bezeichnen wir mit „n“. In unserem Beispiel ist n: 7.
- Beginnen wir mit dem Best Case. Im Best Case liegen die Elemente bereits in sortierter Reihenfolge vor. Der Bubblesort-Algorithmus wird also beim ersten Durchlauf sechs Vergleiche
- durchführen, aber keine Elemente vertauschen. Daraufhin wird er sich sofort beenden.
- Die Anzahl der Vergleiche ist die Anzahl der Elemente minus 1, also n−1. Konstanten wie die −1 können wir bei der Notation der Zeitkomplexität vernachlässigen.
- Die Best-Case-Zeitkomplexität von Bubble Sort lautet also: O(n). Die Komplexitätsklasse O(n) bezeichnen wir als „linear“, da der Aufwand linear mit
- der Anzahl der Elemente wächst. Wo es einen Best Case gibt, da gibt es natürlich auch einen Worst Case.
- Wenn die Elemente zu Beginn komplett absteigend vorsortiert sind, dann haben wir in der ersten Iteration sechs Vergleiche und sechs Vertauschungen.
- Am Ende der ersten Iteration ist die letzte Zahl an der richtigen Position. In der zweiten Iteration haben wir fünf Vergleiche und Vertauschungen, und am Ende sind die zwei
- letzten Zahlen an der richtigen Stelle. In der dritten Iteration haben wir vier Vergleiche und Vertauschungen.
- In der vierten Iteration sind es drei … in der fünften Iteration zwei … und in der sechsten Iteration noch einen Vergleich und eine Vertauschung.
- Insgesamt kommen wir auf 21 Vergleiche und Vertauschungen. Das kann man auch wie folgt ausrechnen: sieben Elemente … mal sechs Iterationen … geteilt
- durch zwei, da pro Iteration im Durchschnitt die Hälfte der Elemente verglichen und vertauscht wird.
- Sieben mal sechs ist 42 … geteilt durch zwei ist 21. Wenn wir „sieben“ wieder durch „n“ ersetzen, ergibt das: n x (n − 1) x ½.
- Ausmultipliziert ergibt das: ½ (n² − n). Für die Notierung der Zeitkomplexität ist nur die höchste Potenz von n relevant, also
- n². Die Worst-Case-Zeitkomplexität von Bubble Sort ist also: O(n²).
- O(n²) − oder auch „quadratischer Aufwand“ − bedeutet: Die benötigte Zeit wächst im Quadrat mit der Anzahl der zu sortierenden Elemente.
- Ein Beispiel: Auf meinem Laptop benötigt Bubblesort für 100.000 absteigend vorsortierte Elemente etwa
- 5,5 Sekunden. Für eine Million Elemente (also zehnmal so viele) braucht es nicht etwa 55 Sekunden,
- sondern etwa 550 Sekunden − also hundert Mal so lang. Für zehn Millionen Elemente würde es 55.000 Sekunden benötigen.
- Und für 100 Millionen Elemente: 5,5 Millionen Sekunden. Das sind ziemlich genau zwei Monate. Quicksort braucht dafür gerade mal zehn Sekunden.
- Rechts oben in der Ecke und auch in der Videobeschreibung findet ihr einen Link zu meinem Quicksort-Video. Die durchschnittliche, also die Average-Case-Zeitkomplexität lässt sich leider nicht auf ganz so anschauliche
- Art und Weise bestimmen. Ohne dies mathematisch zu beweisen kann man grob sagen, dass man im durchschnittlichen
- Fall etwa halb so viele Tauschoperationen hat wie im Worst Case, da sich die Hälfte der Elemente im Vergleich zum Nachbarelement an der richtigen Position befindet.
- Die Anzahl der Tauschoperationen ist also: ¼ (n² – n). Die Anzahl der Vergleichsoperationen lautet wie folgt: …
- Das habe ich von Wikipedia kopiert – und solange ihr nicht Mathe studiert oder euch auf theoretische Informatik spezialisiert, müsst ihr das nicht unbedingt verstehen.
- Was ihr allerdings erkennen solltet, ist, dass in beiden Termen die höchste Potenz von n n² ist.
- Und damit gilt: Auch die Average-Case-Zeitkomplexität von Bubble Sort ist: O(n²). Ich hoffe euch hat dieses Video über Bubblesort gefallen. Auf meiner Webseite HappyCoders.eu
- findet ihr die Erklärung noch einmal zum Nachlesen. Einen Link findet ihr in der Videobeschreibung. In dem Artikel findet ihr auch den Quellcode von Bubble Sort und die Beschreibung zweier
- Ansätze, um Bubblesort zu parallelisieren. In der Videobeschreibung findet ihr auch Links zu meinen weiteren Videos über Sortieralgorithmen.
- Wenn euch das Video gefallen hat, dann gebt mir gerne einen Daumen hoch oder schreibt mir einen Kommentar. Und wenn ihr über neue Videos informiert werden möchtet, abonniert
- gerne meinen Kanal. Bis bald und Happy Coding!