Bubble Sort Algorithmus [mit Animation, Deutsch]
HappyCoders
https://www.youtube.com/watch?v=Mj-payJDsdw

Transkript (automatisch erstellt)

0:00 In diesem Video zeige ich euch wie Bubble Sort funktioniert und wie man die Zeitkomplexität von Bubble Sort bestimmt.
0:08 Wir wollen diese sieben Zahlen mit Bubble Sort sortieren. Wir vergleichen nun, von links beginnend, jeweils zwei Elemente miteinander und tauschen
0:17 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
0:26 wir sie. Die 6 und die 4 stehen ebenfalls nicht in der richtigen Reihenfolge und wir tauschen
0:32 auch diese. Die 6 und 9 stehen in der richtigen Reihenfolge zueinander.
0:38 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
0:46 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,
0:58 sortierten Teil. Wir starten erneut am Anfang des Arrays und vergleichen die 2 mit der 4. Diese liegen
1:05 in korrekter Reihenfolge und müssen nicht vertauscht werden. Das gleiche gilt für die 4 und die 6.
1:12 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.
1:21 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
1:32 Position nach links. Wir starten wieder am Anfang.
1:36 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.
1:46 Die 4 und die 6 liegen bereits in richtiger Reihenfolge. Wir sind wieder am Ende des unsortierten Bereichs angekommen und schieben die Trennlinie weiter
1:55 nach links. Wir beginnen erneut am Anfang.
1:59 2 und 3 stehen in korrekter Reihenfolge; 3 und 1 müssen vertauscht werden; und 3 und 4 stehen in korrekter Reihenfolge.
2:08 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.
2:19 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
2:30 Reihenfolge zueinander. Und damit sind alle Zahlen sortiert und der Bubble-Sort-Algorithmus beendet.
2:36 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
2:48 Luftblasen − englisch „bubbles“. Daher der Name „Bubble Sort“. Kommen wir zur Zeitkomplexität von Bubble Sort.
2:58 Die Anzahl der zu sortierenden Elemente bezeichnen wir mit „n“. In unserem Beispiel ist n: 7.
3:04 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
3:17 durchführen, aber keine Elemente vertauschen. Daraufhin wird er sich sofort beenden.
3:23 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.
3:35 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
3:47 der Anzahl der Elemente wächst. Wo es einen Best Case gibt, da gibt es natürlich auch einen Worst Case.
3:54 Wenn die Elemente zu Beginn komplett absteigend vorsortiert sind, dann haben wir in der ersten Iteration sechs Vergleiche und sechs Vertauschungen.
4:04 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
4:16 letzten Zahlen an der richtigen Stelle. In der dritten Iteration haben wir vier Vergleiche und Vertauschungen.
4:22 In der vierten Iteration sind es drei … in der fünften Iteration zwei … und in der sechsten Iteration noch einen Vergleich und eine Vertauschung.
4:33 Insgesamt kommen wir auf 21 Vergleiche und Vertauschungen. Das kann man auch wie folgt ausrechnen: sieben Elemente … mal sechs Iterationen … geteilt
4:44 durch zwei, da pro Iteration im Durchschnitt die Hälfte der Elemente verglichen und vertauscht wird.
4:51 Sieben mal sechs ist 42 … geteilt durch zwei ist 21. Wenn wir „sieben“ wieder durch „n“ ersetzen, ergibt das: n x (n − 1) x ½.
5:05 Ausmultipliziert ergibt das: ½ (n² − n). Für die Notierung der Zeitkomplexität ist nur die höchste Potenz von n relevant, also
5:14 n². Die Worst-Case-Zeitkomplexität von Bubble Sort ist also: O(n²).
5:22 O(n²) − oder auch „quadratischer Aufwand“ − bedeutet: Die benötigte Zeit wächst im Quadrat mit der Anzahl der zu sortierenden Elemente.
5:31 Ein Beispiel: Auf meinem Laptop benötigt Bubblesort für 100.000 absteigend vorsortierte Elemente etwa
5:39 5,5 Sekunden. Für eine Million Elemente (also zehnmal so viele) braucht es nicht etwa 55 Sekunden,
5:48 sondern etwa 550 Sekunden − also hundert Mal so lang. Für zehn Millionen Elemente würde es 55.000 Sekunden benötigen.
5:58 Und für 100 Millionen Elemente: 5,5 Millionen Sekunden. Das sind ziemlich genau zwei Monate. Quicksort braucht dafür gerade mal zehn Sekunden.
6:09 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
6:22 Art und Weise bestimmen. Ohne dies mathematisch zu beweisen kann man grob sagen, dass man im durchschnittlichen
6:29 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.
6:40 Die Anzahl der Tauschoperationen ist also: ¼ (n² – n). Die Anzahl der Vergleichsoperationen lautet wie folgt: …
6:49 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.
6:59 Was ihr allerdings erkennen solltet, ist, dass in beiden Termen die höchste Potenz von n n² ist.
7:06 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
7:19 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
7:30 Ansätze, um Bubblesort zu parallelisieren. In der Videobeschreibung findet ihr auch Links zu meinen weiteren Videos über Sortieralgorithmen.
7:39 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
7:48 gerne meinen Kanal. Bis bald und Happy Coding!