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
Tipp auf eine Zeit – das Video springt genau dorthin.
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!
Zum Nachlesen
BubblesortBubblesort (auch Sortieren durch Aufsteigen oder Austauschsortieren) ist ein Algorithmus, der vergleichsbasiert eine Liste von Elementen sortiert.
GnomesortGnomesort ist ein sehr einfacher und stabiler Sortieralgorithmus. Animation von Insertionsort bzw. von Gnomesort ohne Visualisierung der …
ShakersortDer Begriff Shakersort bezeichnet einen stabilen Sortieralgorithmus, der eine Menge von linear angeordneten Elementen (z. B. Zahlen) der Größe nach sortiert …
Swap-SortSwap-Sort ist ein Sortieralgorithmus, der ein Array aus paarweise verschiedenen Zahlen sortiert. Inhaltsverzeichnis. 1 Idee; 2 Prinzip; 3 Beispiel …