Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Quicksort Algorithmus [mit Animation, Deutsch]
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 81 Zeilen
- In diesem Video zeige ich euch, wie Quicksort funktioniert, was ein Pivot-Element ist und wie man es festlegt und wie man die Zeitkomplexität von Quicksort bestimmt.
- Wir wollen diese neun Zahlen mit Quicksort sortieren. Dazu teilen wir die Zahlen in zwei Bereiche auf: einen mit kleinen Zahlen und einen mit
- großen Zahlen. Und danach sortieren wir diese Bereiche – in sich – wiederum mit Quicksort. Aber was sind kleine und große Zahlen?
- Um diese voneinander abzugrenzen, legen wir ein sogenanntes “Pivot-Element” fest. Dafür gibt es verschiedene Strategien – zu denen kommen wir später.
- Die einfachste ist: Wir verwenden immer das Element ganz rechts – im Beispiel also die 6.
- Kleine Zahlen sind jetzt alle Zahlen, die kleiner als 6 sind und große Zahlen sind die, die größer oder gleich 6 sind.
- Um die Zahlen in zwei Bereiche aufzuteilen, gehen wir wie folgt vor: Wir suchen von links beginnend nach dem ersten Element, das größer oder gleich 6 ist.
- Die 3 ist es nicht; die 7 ist größer als 6. Und von rechts beginnend, suchen wir das erste Element, das kleiner als 6 ist.
- Das Pivot-Element selbst überspringen wir. Und mit der 4 haben wir die erste Zahl kleiner als 6 gefunden.
- Jetzt tauschen wir die 7 und die 4, so dass die 4 im linken Bereich landet und die 7 im rechten.
- Wir suchen von links das nächste Element, das größer oder gleich 6 ist. Die 1 ist es nicht; die 8 ist größer als 6.
- Und von rechts das nächste Element kleiner als 6. Die 9 ist nicht kleiner, die 5 ist kleiner.
- Wir tauschen also die 8 und die 5. Wir setzen die Suche von links fort. Bei der 2 angekommen stehen die Suchpositionen direkt
- nebeneinander, d. h. dass wir keine weiteren Elemente tauschen müssen. Die 2 ist kleiner als das Pivot-Element und gehört damit in den linken Bereich.
- Entsprechend fügen wir eine gedankliche Trennlinie rechts von der 2 ein. Und jetzt sind alle Elemente im linken Bereich kleiner als 6 – und alle Elemente rechts
- größer als 6. Ein letzter Schritt fehlt noch bei der Aufteilung. Und zwar wissen wir an dieser Stelle, dass
- alle Elemente im rechten Block größer oder gleich dem Pivot-Element sind – so haben wir sie hier ja einsortiert.
- Im Umkehrschluss ist das Pivot-Element also das kleinste Element des rechten Bereichs – bzw. eines der kleinsten, wenn der Bereich mehrere Sechsen enthalten würde.
- Wenn wir das Pivot-Element nun mit dem ersten Element des rechten Bereichs tauschen, dann liegt es automatisch auf seiner endgültigen Position. Und wir müssen nur noch die Bereiche
- links und rechts des Pivot-Elements sortieren. Wir machen mit dem linken Bereich weiter und bestimmen zunächst wieder das Pivot-Element.
- Entsprechend unserer Pivot-Strategie nehmen wir wieder das letzte Element des Bereichs – die 2.
- Wir suchen wieder von links aus das erste Element, das größer oder gleich 2 ist. Das ist direkt das erste, die 3. Und von rechts aus, das erste Element kleiner als 2 – das
- ist die 1. Wir tauschen die 3 mit der 1.
- Die linke Suchposition wandert noch ein Feld nach rechts und steht damit direkt neben der rechten Suchposition. Wir müssen also keine weiteren Elemente tauschen.
- Die 4 ist größer als das Pivot-Element, gehört damit in den rechten Bereich; und entsprechend ziehen wir die Trennlinie links von der 4.
- Wir tauschen wieder das Pivot-Element mit dem linken Element des rechten Bereichs und trennen auch den Bereich rechts vom Pivot-Element ab.
- Der linke Teilbereich enthält nur die 1 und gilt damit als sortiert. Im rechten Teilbereich wählen wir wieder das Pivot-Element – die 4.
- Wir suchen von links aus das erste Element größer oder gleich 4 – das ist die 5. Damit sind wir auch schon am rechten Rand angekommen, und müssen von rechts nicht mehr
- suchen. Da die 5 größer als das Pivot-Element ist, ziehen wir die Trennlinie links davon.
- Im rechten Teilbereich tauschen wir das Pivot-Element mit dem linken Element – und trennen auch den Bereich rechts vom Pivot-Element ab.
- Und jetzt haben wir im gesamten linken Bereich nur noch Pivot-Elemente und Teilbereiche, die genau ein Element enthalten.
- Der linke Bereich ist damit fertig sortiert. Kommen wir zum rechten Bereich.
- Wir wählen wieder das Pivot-Element. Wir suchen von links das erste Element, das größer oder gleich 8 ist. Das ist direkt
- das erste Element, die 9. Und von rechts suchen wir das erste Element, das kleiner als 8 ist. Das ist die 7, und wir tauschen diese mit der 9.
- Die Suchpositionen sind aufeinander getroffen, und wir ziehen die Trennlinie dazwischen. Im rechten Bereich tauschen wir wieder das Pivot-Element mit dem linken Element und trennen
- den Bereich rechts davon ab. Jetzt haben wir auch im rechten Bereich nur noch Pivot-Elemente und Teilbereiche mit nur
- einem Element. Auch der rechte Bereich ist damit fertig sortiert – und damit die gesamte Liste.
- Der Quicksort-Algorithmus ist damit beendet. Zu Beginn des Videos habe ich erwähnt, dass es verschiedene Pivot-Strategien gibt.
- Im eben gezeigten Beispiel haben wir immer das ganz rechte Element als Pivot-Element gewählt.
- Alternative Strategien sind: das mittlere Element; das linke Element; ein zufälliges Element, der Median aus drei Elementen, z. B. dem ersten, mittleren und letzten – oder
- der Median aus fünf oder sogar sieben Elementen. Das Ziel ist es, das Pivot-Element so zu wählen, dass die Eingabe in zwei möglichst gleich
- große Bereiche aufgeteilt wird. Bei zufällig verteilten Eingabezahlen macht es keinen Unterschied, ob man das linke, mittlere
- oder rechte Element wählt. Nimmt man den Median aus drei Zahlen, dann erhöht man die Wahrscheinlichkeit, dass die
- Bereiche ähnlich groß sind. Sind die Eingabeelemente jedoch vorsortiert, kann es zu Problemen kommen.
- Nehmen wir diese Eingabe. Wenn wir das rechte Element, also die 9, als Pivot-Element wählen, dann hat nach der Partitionierung
- der linke Bereich acht Elemente und der rechte gar keine. Wenn wir dann den linken Bereich partitionieren, erhalten wir einen Bereich mit sieben Elementen.
- Dann einen mit sechs, mit fünf, mit vier, usw. Insgesamt müssen wir acht mal partitionieren. Das ist doppelt so viel wie bei den zufällig verteilten Zahlen, bei denen wir nur vier
- mal partitioniert haben. Das gleiche passiert, wenn wir das linke Element als Pivot-Element verwenden – oder wenn
- die Bereiche absteigend vorsortiert sind. Wenn also die Möglichkeit besteht, dass unsere Eingabezahlen vorsortiert sind, dann sollten
- wir auf keinen Fall das linke oder rechte Element als Pivot-Element wählen, sondern das mittlere, ein zufälliges oder den Median aus mehreren Elementen.
- Kommen wir zur Zeitkomplexität von Quicksort – und zwar zuerst zum worst case, den wir eben bei den vorsortierten Elementen gesehen haben.
- Die Anzahl der zu sortierenden Elemente bezeichnen wir mit “n”. Im folgenden Beispiel ist n gleich sieben.
- Bei der ersten Partitionierung vergleichen wir sechs Elemente mit dem Pivot-Element. . Es entsteht ein einziger Bereich mit sechs
- Elementen. Bei der zweiten Partitionierung vergleichen wir fünf Elemente mit dem Pivot-Element.
- Bei der dritten Partitionierung vergleichen wir vier Elemente, bei der vierten drei Elemente, bei der fünften zwei Elemente und bei der sechsten noch ein Element.
- In der Summe kommen wir auf 21 Vergleiche. Das kann man auch wie folgt ausrechnen: sieben Elemente mal sechs Partitionierungsschritte
- – geteilt durch zwei, da pro Partitionierungsschritt im Durchschnitt die Hälfte der Elemente verglichen wird.
- Sieben mal sechs ist 42 – geteilt durch zwei ist 21. Wenn wir “sieben” wieder durch “n” ersetzen, ergibt das: n × (n-1) × ½
- Ausmultipliziert ergibt das: ½ (n² – n) Für die Notierung der Zeitkomplexität ist nur die höchste Potenz von n relevant, also
- n². Die Zeitkomplexität von Quicksort ist also im worst case (auf deutsch: im schlechtesten
- Fall): O von n Quadrat. O von n Quadrat … oder auch “quadratischer Aufwand” bedeutet: Die benötigte Zeit wächst
- im Quadrat mit der Anzahl der zu sortierenden Elemente. Als nächstes schauen wir uns den best case an. Im besten Fall sind die bei der Partitionierung
- entstehenden Bereiche immer gleich groß. Hier wieder unser Beispiel mit sieben Elementen.
- Bei der ersten Partitionierung vergleichen wir sechs Elemente mit dem Pivot-Element; und es entstehen zwei Bereiche mit jeweils drei Elementen.
- Bei der Partitionierung des linken und rechten Bereichs vergleichen wir jeweils zwei Elemente mit den jeweiligen Pivot-Elementen. Es entstehen vier Bereiche der Größe eins.
- Und damit sind wir auch schon fertig. In der Summe kommen wir auf nur zehn Vergleiche. Im worst case waren es 21.
- Aber wie verpacken wir das jetzt in eine Formel? Wir haben hier zum einen mehrere Ebenen und zum anderen eine Anzahl von Vergleichen und
- ggf. Vertauschungen pro Ebene. Wenn wir die Anzahl der Elemente auf 14 verdoppeln, dann müssen wir nur eine Zeile hinzufügen;
- und die Anzahl der Vergleiche pro Zeile verdoppelt sich … ungefähr (in diesem Beispiel ist es jeweils einer weniger als das Doppelte).
- Wenn wir mit nur einer zusätzlichen Partitionierungsebene doppelt so viele Elemente sortieren können, entspricht im Umkehrschluss die Anzahl der Partitionierungsebenen dem Zweierlogarithmus
- von n. Für die O-Notation kann die Basis wegfallen, und wir erhalten: O(log n)
- Die Anzahl der Operationen pro Partitionierungsebene wächst, wie wir gesehen haben, linear mit n.
- So wie man die Fläche eines Rechtecks durch Multiplikation von Breite und Höhe berechnet, können wir für den Gesamtaufwand die Operationen pro Partitionierungsebene mit der Anzahl der
- Ebenen multiplizieren. Als Zeitkomplexität für den Best Case ergibt sich also: O von n mal log n
- Wir nennen diese Komplexitätsklasse auch “quasilinearen” Aufwand, da bei großen n der logarithmische Anteil kaum noch ins Gewicht fällt und die Kurve kaum noch von
- einer Linearen zu unterscheiden ist. Auch im average case, also im durchschnittlichen Fall, lautet die Zeitkomplexität O von n
- log n. Der Nachweis ist allerdings … recht kompliziert und würde den Rahmen dieses Videos sprengen.
- Ich hoffe euch hat diese Erklärung von Quicksort gefallen. Ihr findet die Erklärung nochmal zum Nachlesen auf meiner Webseite HappyCoders.eu. Einen Link gibt es in der Videobeschreibung.
- In dem Artikel findet ihr auch den Quellcode von Quicksort und die Beschreibung einer fortgeschrittenen Quicksort-Variante, dem Dual-Pivot-Quicksort.
- Wenn euch das Video gefallen hat, dann freue ich mich über einen Daumen hoch oder einen Kommentar, und natürlich auch, wenn ihr meinen Kanal abonniert.
- Bis bald und Happy Coding!
Zum Nachlesen
QuicksortQuicksort (englisch quick ‚schnell' und to sort ‚sortieren') ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile …
AlgorithmusAlgorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten. ... Damit können sie zur Ausführung in ein Computerprogramm implementiert, aber auch in …