Video 7-7: Quicksort

0:01 Im nächsten Abschnitt schauen wir uns Quicksort an. Wie der Name vielleicht schon prognostiziert, äh oft der schnellste Algorithmus in der Praxis zum ähm sortieren, wenn man keine speziellen Anforderungen hat. Und ein bisschen zur Geschichte dazu, ähm der Erfinder von Quicksord ist Tony Hor, der äh im März diesen Jahres verstorben ist. Ähm, aber man sieht von ihm noch ähm einige ein Interviews und Zeugnisse, wenn ich noch drauf zurückkomme, wo er auch erklärt, wie es äh zu diesem zu dieser Erfindung kam. Äh gibt eine ganz interessante Geschichte dazu und insbesondere auch sein äh sein Forschungspaper, welches ist gar nicht hier drauf. Schade. Äh von 1962 hat er ein Forschungsartikel geschrieben, indem der Algorithmus erklärt wird. Der ist durchaus lesenswert auch heute noch, ne?

1:10 Indem er auch sehr viele Dinge äh über seinen Algorithmus und über Methoding und so weiter hinaus vorweggenommen hat. Aber gut. Ähm, ich be lass die Geschichte kurz und gebe ihn ein paar Pointer, wo sie das bisschen nachlesen können. Äh, Robert Setchwick, der für das eine Buch, nachdem an dem ich mich auch orientiere und für einige der Folien hier verantwortlich ist, hat selbst über Quicksot promoviert und ich dann auch. Insofern gibt's da viel ähm persönliche Verbindungen dazu. Äh und Robert Ctrick hat im im Wesentlichen die mathematische Analyse von Quicksot auf solide Beine gestellt. Ähm wo sozusagen in dem Originalpaper von Tony H einiges schon drin ist, aber für die praktisch relevanten äh Varianten noch Dinge offen waren und unklar waren. Äh, wenn Sie all das ein bisschen mehr interessiert, äh, dann können Sie dazu ein paar Videos anschauen. Es gab eine einen Mini Workshop zum 60-jährigen Jubiläum oder zum 60-jährigen Geburtstag von Quicksot und äh das Jahr werden Sie wieder erkennen als eins, indem man diese Dinge eben online und aufgezeichnet hat, was den schönen Effekt hat, ähm dass man die sich noch anschauen kann.

2:25 Und da gab's eben äh im Wesentlichen diese vier Vorträge bzw. ein ein Übersichtsvortrag von Setwick, was man so über Quicksot mittlerweile weiß. Äh ich hatte auch einen Beitrag über Dinge, zu denen ich noch bisschen was sagen werde. Quicksot in Java und am Ende hat Tony Hor dann Fragen beantwortet über sein Algorithmus. Ähm hat viel Spaß gemacht. Ob die Aufzeichnung genauso viel Spaß macht, kann ich ähm kann ich Ihnen nicht sagen, aber sie können es ausprobieren. Ich habe die Videos noch mal neu hochgeladen in geschnitten, die gab's schon von diesem Workshop, aber als so ein langes, wenig bequem verwendbares ähm langes Video. Ähm, wenn Sie da Spaß dran haben, schauen Sie mal rein. Aber jetzt erst noch mal ein Schritt zurück. Was ähm wie könnte man Quicksot motivieren? Es gilt gilt unter den weit verbreiteten Algorithmen als der am wenigsten intuitive. Deswegen hier mein Versuch es noch mal ähm bisschen anders zu motivieren, als das vielleicht sonst gemacht wird.

3:26 Werden uns über Selection Sort unterhalten. Sehnen sich ähm wie funktioniert das? Ich habe ein Element, wo ich mir merke, wo das bisher kleinste Element ist. Das schiebe ich so durch die Eingabe und wann immer ich was noch kleineres finde, dann tausche ich äh merke ich mir sozusagen, hier war jetzt das Minimum und in dem Fall ist die eins das kleinste. Das heißt, ich komme ganz am Ende an und jetzt habe ich das kleinste Element gefunden. Das kann ich an den linken Rand tauschen. Damit bin ich dieses Element los. Und dann mache ich iterativ, man könnte auch sagen rekursiv mit dem gleichen Algorithmus auf dem Rest der Eingabe weiter. Äh eine Runde machen wir noch. Wir suchen wieder das Minimum und ich schiebe weiter, bis ich hier ein anderes Minimum gefunden habe, noch ein Minimum und so weiter. Wenn ich durch das Array durch bin, wieder einmal rechts angekommen, habe ich das nächst kleinste Element gefunden und kann es an den linken Rand tauschen.

4:20 Super. Ähm zieht sich nur so ein bisschen, bis man das äh geschafft hat. Sie erkennen optisch und hatten wir damals ja auch schon diskutiert, dass es ein quadratisches Verfahren n quadrat halbe Vergleiche. Das skaliert nicht gut. Äh, worum es mir hier geht, ist in einem Schritt haben wir n -1 Vergleiche gemacht, insbesondere der erste Schritt. Schauen uns mal den ersten Schritt an. N - 1 Vergleiche. Und was wir daraus äh an Informationen gezogen haben, ist das Minimum zu finden, was uns dann erlaubt hat, ein Element loszuwerden. Das ist halt nicht so gut. Das ist auch der Grund, warum der Algorithmus nicht so schnell ist. Was könnte ich denn noch mit n- 1 vergleichen tun?

5:05 Wenn man das Minimum vorher schon kennt, dann kann ich mit n - 1 vergleichen verifizieren, ob das Element das Minimum ist da. Na ja, äh ich kann aber auch irgendein anderes Element nehmen und zählen, wie viele Elemente kleiner sind. Passt das gleiche. Ähm braucht auch die gleiche Anzahl Vergleiche. Äh, das ist die Basisidee, auf der Quicksot aufbaut. Machen wir das hier mal an dem Beispiel. Also, wir wählen das erste Element aus und jetzt vergleichen wir alle anderen mit diesem Element, ne? Das halt manches ist kleiner und manches ist größer, wie auch immer. Und dann weiß ich jetzt hinterher von allen Elementen, ob sie größer oder kleiner sind. Das ist noch nicht sortieren, ne? Aber ich weiß jetzt, dass es genau vier Elemente gibt, die kleiner sind als die fünf und die anderen vier der verbliebenen sind größer. Das heißt, ich weiß jetzt genau, wo die fünf in der sortierten Reihenfolge hin muss, nämlich zwischen diese an die Position fünf, wenn man so will.

6:05 Das heißt, wenn ich mal von diesem Schritt abstrahiere, wie wir das genau machen, kann ich alle die Elemente, die kleiner sind, nach links packen und alle, die größer sind, nach rechts. Und wie gesagt, der Zauberstab wird noch ersetzt. Dann ist die fünf zwischen diesen an der Position, an der sie in der komplett sortierten Folge stehen bleiben muss. Ja, weil genau alle kleineren links von sind und alle größeren rechts davon. Und wir haben tatsächlich noch mehr geschafft, denn dadurch, dass jetzt hier alle Links von diesem von dieser fünf kleiner als fünf sind und alle rechts davon größer, kann ich diese zwei Bereiche unabhängig voneinander sortieren. Ich werde nie mehr die 2 und die sech vergleichen müssen. Ich weiß schon, was da rauskommt. Die fünf war ja dazwischen. Ja, das heißt, ich habe mit der gleichen Anzahl n - 1 vergleichen hier plötzlich viel mehr Fortschritt erzielt. Ich habe ein Element an die endgültige Position gebracht. Das hatte auch Selection Sord geschafft. Aber Selection Sord hatte über die restliche Eingabe gar nichts gelernt. Während hier haben wir jetzt gelernt, dass ä die eine Hälfte kleiner, die andere größer ist.

7:15 Dann muss man auch hier ähm wieder die verbliebenen Teile mit dem gleichen Verfahren rekursiv sortieren. Das sind jetzt hier mal zwei Aufrufe, statt nur ein, aber das kann Rekursion ja gut. Das heißt, wir schauen uns den Teil an, machen das gleiche wieder. Wir wählen ein Element und schauen, wie viele sind. Okay, das ist irgendwie falsch, ne? Ähm, da sind die Zahlen vertauscht. Tun wir mal so, als wäre die zwei das Element, was wir ausgewählt haben und nicht die 1. Dann wäre ein Element kleiner und hier müsste die ein stehen und ähm hier die drei. Ähm abgesehen davon, nehmen wir mal an, das wäre so. Wäre die zwei jetzt hier an der endgültigen Parkposition und die anderen müssen wir rekursiv sortieren. Wenn dieser linke Teil nur ein Element ist, brauchen wir dann nichts mehr machen. Das ist schon sortiert. Okay, hier haben wir noch mal einen Aufruf und dann müssen wir uns aber die ganze Zeit durch haben wir uns gemerkt, dass hier rechts noch eine noch eine Aufgabe auf den Tod-Do Stapel wartet, ne? So, der müssen wir dann irgendwann zurückkehren.

8:24 Mal gucken, ob ich noch mehr in der Animation verhauen habe. Na, das passt. Also auch die acht wieder ähm verglichen mit den Elementen und entsprechend einsortiert und so weiter.

8:38 Die lange Animation hier sollte Ihnen zwei Dinge zeigen. Erstens, wir müssen uns über teilweise lange Zeiträume merken, da hinten gibt's noch so einen Bereich, den ich noch sortieren muss. Das müssen wir irgendwie lösen. Zweitens, die Gesamtanzahl Vergleiche, die man da typischerweise braucht, ist viel viel kleiner, weil man zwar im ersten Schritt gleich viele Schritte, gleich viele Vergleiche macht, aber es sehr viel mehr vorankommt nach diesem einen Schritt.

9:05 Okay, das ist so die Idee. Ähm, für dieses erste Problem, das Verwalten, welche Teile ich noch rekursiv sortieren muss, nehme ich halt Rekursion. Das macht genau das, was man hier möchte. Ich habe das an dem Beispiel nur deshalb noch ein bisschen ausführlich erklärt, weil das ähm motiviert, warum Quicksort erst so spät erfunden wurde, erst 1960, 1961, während Merchsort schon Ende Ende der 40er Jahre bekannt war. Äh dazu gleich noch ein bisschen was. Ähm, erstmal kurz den Code. Wir haben einen globalen Aufruf, der beim Wesentlichen dann die Kontrolle weitergibt an einen rekursiven Aufruf wie beim Merch Sort, wo ich die ähm einen Bereich in meinem Array sortiere. Also, der allgemeine Fall ist, wir sortieren in A von L bis R und hier jetzt mit der in Java üblicheren Konvention, dass der Endindex exklusive ist. Wenn meine Anzahl Elemente in diesem Bereich nur eins ist, dann brauche ich nichts mehr tun. Und für die anderen Fälle ähm habe ich vorher eine komplett unsortierte Eingabe, mit meinem Gewackelbild.

10:23 Dann rufe ich eine Funktion auf, über die wir gleich noch reden müssen, die das macht, was hier dieser magische Zauberstab irgendwann mal getan hat, nämlich die Elemente, die kleiner sind, an den linken Rand bringen, die Elemente, die größer sind, an den rechten Rand bringen. Und das Element, das wir uns gerade anschauen, das Pivotelement, den Namen hatte ich bisher nicht erwähnt, einfach das der Dreh und Angelpunkt wortwörtlich. ähm zwischen diese zwei Bereiche, das nennt man partitionieren, weil ich eben dann die kleinen von den großen Elementen trenne.

11:09 Das rufe ich hier einmal auf. Bildlich gesprochen macht partitionieren das hier. Ich habe ein Pivotelement hier. Das steht am Ende zwischen allen Werten, die kleiner sind und allen, die größer sind. Und gleichzeitig ist dann alles, was rechts von dem Pivot steht, auch oberhalb der Linie dieses Pivot einzeichnet und alles links davon unterhalb. Na ja, dann habe ich rekursive Aufrufe, die stehen hier im Code auch noch mal ausgeführt. Die machen genau das, was Rekursion eben tut. Wenn man das äh in dieser Animation so malt mit das ist noch zu tun und das ist noch zu tun, dann wirkt es kompliziert. Aber mit Rekursion ist es das nicht. Der der witzige Teil dabei oder der spannende Teil dabei ist, dass Tony H die Idee für Quicksort und das Partitionieren hatte, bevor er wusste, was Rekursion ist. Das war da noch nicht so geläufig und er hat dann erst über eine Programmiersprache Algol 60 kennengelernt, dass es Rekursion gibt und plötzlich ähm fiel es ihm dann wie Schuppen von den Augen, dass das genau das ist, was man hier für Quicksot haben will.

12:13 Also ein bisschen zeigt vielleicht noch, er hat da noch live von berichtet vor ein paar Jahren, wie er das entdeckt hat, weil Rekursion noch nicht bekannt war. ähm zeigt so ein bisschen, wie wie jung viele Sachen in der Informatik sind, die wir heute so ein ich hoffe auch in ihr aus ihrer Sicht als einfaches Konzept ansehen, was man so das lernt man mal und am Anfang ist verwirrend, aber dann hat man es so verinnerlicht, dass man es sich w schwer vorstellen kann, es nicht zu kennen. Okay, also das ist der Teil von Quicksort, wenn man das Partitionieren schon erledigt hat. Jetzt müssen wir uns über diesen Zauberstab noch unterhalten und wir machen erst eine einfache Version, die ähm deshalb einfacher ist, weil sie sich ein bisschen extra Platz gönnt. Äh da gibt's so ein paar Java spezifische Sachen, ähm auf die ich gleich noch kurz eingehen werde, aber für den Moment fokussieren sich mal auf den hervorgehobenen Teil.

13:17 Äh, wir erlauben uns Zusatzspeicher, das heißt äh ein Pufferbereich für die kleinen Elemente und Pufferbereich für die großen Elemente. Dann iteriere ich einmal durch mein Teilstück von meinem Array. Ich sortiere ja nur diesen ähm auch das Partitionieren schaut sich nur dieses Stück von L bis R exklusive an.

13:45 Dann ma ich immer den Vergleich, wenn mein aktuelles Element kleiner ist als das Pivot, dann packe ich es zu den kleinen Elementen und ansonsten packe ich es zu den großen Elementen einfach. Und am Ende muss ich die zurückkopieren, weil ich wollte ja in meinem Array A diese partitionierte Reihenfolge haben.

14:05 Ähm, das heißt, ich muss einmal die kleineren Elemente und die größeren Elemente an die passende Stelle kopieren. Und passende Stelle ist eben jetzt dadurch gegeben, dass ich mitgezählt habe, wie viele kleinen und großen Elemente es gibt.

14:22 Okay, ein paar Kommentare zu zu den Details im Code noch ähm ein algorithmischer Teil noch. Ihen ist vielleicht aufgefallen, dass ich da nirgends das Pivotelement zwischen die kleinen und großen Elemente geschrieben habe. Taucht hier im Code nirgends auf. Der Punkt ist, dass das Pivot immer kleiner gleich sich selbst ist. Das heißt, es wird einfach bei den großen mit mit eingebaut irgendwo. Das ist nicht ganz, was wir gerne hätten. Ähm, wir werden aber die Methode sowieso nicht verwenden und so war es ein bisschen einfacher zu formulieren.

15:17 Es ist zufälligerweise, wenn Sie mögen, kein Problem, weil wir von weil wir als Pivot hier das linkeste Element nehmen. Das ist das, was wir als erstes anschauen. Das heißt, das Pivot wird immer das erste in den großen Elementen sein.

15:42 Das heißt, der Algorithmus tut, was er soll, aber es ist so ein bisschen äh wenig robust wegen der Wahl des Pivots hier. Ähm wichtig für die Rekursion, ich muss wissen, welche Aufrufparameter die Rekursion kriegt. Also, wo ist die Grenze, an der das Pivot liegt? Das war hier der Rückgabewert von dieser Partitionsmethode. Den muss ich also auch liefern. Das tue ich hier auch. Das ist nämlich der linke Rand plus die Anzahl kleine Elemente. So viel überspringe ich, dann kriege ich die Position des Pivots zurück.

16:27 Ähm, das ist so ein Fall von Don't do this at home kids. Diese diese Art das Pivot zu wählen ist aus diversen Gründen schlecht. Da kommen wir noch drauf zurück, um den Code einfach zu halten, hier so belassen. Aber ich möchte ähm darauf hinweisen, dass man das so nicht machen möchte. Aber da werden wir noch im Detail nächste Woche drüber reden. Sein Sie erstmal äh, dass wir hier das einfach halten. Ähm, dann gibt's noch so ein paar Kommentare über Java spezifischen Blödsinn. M Wir hätten gerne hier ob Arrays vom generischen Typ Elem, also diese Elemente, die wir sortieren. Das kann Java halt nicht, kennen sie, glaube ich, ne? oder sie machen es noch dieses Semester. Ähm ist ist was Sie in objektorientierter Programmierung im Detail noch besprechen. Ähm im Prinzip ist es eine Beschränkung von Java, weil Generics diese Typarameter erst später hinzugekommen sind, ist es so ein bisschen ein Hack geblieben. Das heißt, das funktioniert nicht, dass man new Elm Array schreibt, auch wenn man das hier gerne hätte. Man kann also nur Object Arrays anlegen und mit einem Cast dann äh so tun, als sei das ein Elm Array. Und das funktioniert auch. Das braucht sie sozusagen nicht bekümmern, aber der Compiler wirft ihn immer eine Warnung, weil dieser Cast unchecked ist.

17:51 Ich kann nicht statisch garantieren, der Compiler kann es nicht, dass dieses Array nicht äh auch andere Objekte enthält als Elm Objekte. istich ein bisschen doof, weil ich lege ihn gerade hier an und mache dann direkt den Cast. Niemand kriegt seine Finger auf dieses Ding. Niemand kann dieses Array modifizieren oder andere Objekte reinstecken. Äh, aber statisch ähm kann es der Compiler nicht entscheiden. Dementsprechend gibt er die Warnung aus und dieses Suppress Warnings unterdrückt die Warnung, weil wir hier überschreiben menschliches äh menschliche Expertise, wir wissen, was wir tun. Ähm, belehre uns nicht über diesen über deine eigene Unzulänglichkeit. Äh, zweiter Kommentar sind diese ähm Array Copy Aufrufe. Das könnte man auch ersetzen durch eine Schleife, die durch die durch die Arrays iteriert und die Elemente zurückkopiert, wie wir es in Merch auch hatten. Ähm, in der Praxis ist das ein bisschen schneller, weil das einen internen Aufruf generiert, der das auf Betriebssystemebene ein bisschen lowleveliger macht, als man es in Java tun könnte.

18:56 Ähm, sollten sie also in Betracht ziehen, wann immer sie große Arrays kopieren, lohnt sich es wahrscheinlich das mit Array Copy zu machen. Und die ähm die Parameter haben eben die Bedeutung, ich kopiere von A ab Position I nach B ab Position J Nel Elemente und sie dürfen das für beliebige Objekte aufrufen. Deswegen ist das so ein bisschen äh das ist nicht die echte Signatur, aber das ist die, wie man sie ähm wie man sie lesen muss. Also für die Experten Array Copy akzeptiert sowohl primitive Array Typen, also int Array als auch object Array. Und es gibt keinen Array Typ, der das gemeinsam darstellt, außer Object ohne Array. Das heißt, die machen dann auch wieder irgend so einen internen äh dreckigen Cast, aber funktioniert und ist oft schneller als diese das Kopieren in dem in der Schleife.

20:02 Okay, also grundsätzlich funktioniert Partitionieren so und ist auch kein schwieriger Algorithmus. Äh, es gab so ein paar ähm Bemerkungen hier, die sozusagen sagen, wollen wir so nicht verwenden. Ähm, insbesondere aber ist dieser Zusatzspeicher hier eigentlich lästig.

20:20 Hatten wir beim Merchort akzeptiert, aber ich sage Ihnen hier, es geht besser. Man kann dieses diesen Partitionierungsschritt auch komplett ohne Zusatzspeicher machen, indem man ein bisschen cleverer ist. Und das ist der Teil, wo Tony Hor sagt, das war der einfache Teil. Das hatte ich mal schnell runtergeschrieben in Assembly auf so einer komischen Maschine. Ähm, überlasse ich Ihnen, ob Sie den Teil einfacher fanden oder die Rekursion. Äh, aber ich ich kann Ihnen das kurz erklären. Das ist wirklich Grund von der von der Idee her einfach, nur die Details sind ein bisschen fummeliger. Wir wählen wieder unser Pivotelement und jetzt müssen wir konzeptionell alle Elemente mit dem Pivot vergleichen. Die kleinen nach links und die großen nach rechts bringen. Wir machen das jetzt aber hier ähm ohne Zusatzspeicher, indem wir nur Elemente vertauschen. Erstmal fangen wir auf der linken Seite an. Das ist ein Element, das kleiner ist als das Pivot. Das ist gut. Es ist links und klein. Das heißt, es kann im Wesentlichen bleiben, wo es ist.

21:20 Deswegen lassen wir es auch da und gehen einfach zum nächsten Element über. In dem Fall ist es natürlich ein großes, das ist größer als das Pivot. Das muss also irgendwann nach rechts. Aber statt jetzt anzufangen, das direkt irgendwo da nach hinten zu vertauschen, machen wir was clevereres. Wir fangen jetzt auf der rechten Seite an und suchen einen passenden Partner für dieses Element. Das hier muss irgendwann darüber, aber wohin genau? Das können wir uns ja noch überlegen. Das heißt, wir halten hier einfach mal den einen Index an und fangen mit einem zweiten von rechts an. Der kann nämlich jetzt hier, wenn das ein großes Element ist, das einfach stehen lassen und das diese zwei zu tauschen wäre jetzt eine doof Idee gewesen. Stattdessen lassen wir das große hier und gehen zum nächsten über, bis wir ein kleines Element finden, was wiederum hier nicht stehen kann. Jetzt habe ich ein paar von Elementen, die beide falsch sind. Dann vertausche ich die einfach und dann sind sie beide happy.

22:19 Okay, das ist so der Kerntrick. Das vermeidet unnötige Vertauschung. Äh ansonsten ähm funktioniert es das Ganze wie beschrieben einfach weiter. Ich nehme das nächste Element. Das ist wieder klein, kann stehen bleiben. Wieder klein, kann stehen bleiben. Bis ich das nächste große habe, dann muss ich wieder von rechts anfangen. Bei von rechts heißt das A. Groß ist gut, kann stehen bleiben. Klein ist nicht gut, muss ich tauschen. Habe ich noch einen Tausch und jetzt haben sich diese diese zwei Indizes getroffen und sobald das passiert ist, weiß ich, dass ich fertig bin. Zumindest fast. Ähm, ein Schritt fehlt noch, nämlich das Pivot zwischen diese beiden bringen. Das könnte man jetzt auf doof Weise machen, indem man die alle eins nach links rückt, aber die sind ja eh noch nicht sortiert. Also kann ich einfach das letzte mit dem Pivot tauschen, dann sind sie immer noch nicht sortiert, aber das Pivot steht jetzt an der passenden Stelle.

23:20 Wir sehen kein Zusatzspeicher nötig, nur Vertauschung und ein bisschen clevere Indics, zwei Indic und das Pivot müssen wir uns merken und das war's. Also sozusagen drei Variablen. Wir betrachten auch in diesem Durchgang, obwohl wir so von links und rechts immer wieder mal halb machen, jedes Element im Wesentlichen einmal. Ich vergleiche es einmal mit dem Pivot und dann mag es eventuell noch mal vertauscht werden. Da warte ich vielleicht kurz, aber ich ich werde es nicht noch mal anfassen. Und ich weiß auch, wo das Pivot hingehört, nämlich da, wo sich die Zeiger treffen. Und ähm in Code kann man das so ausdrücken, indem man eine äußere Schleife hat, die läuft, bis sich diese Zeiger getroffen haben. zwei innere Schleifen, die dieses von links nach rechts oder von rechts nach links vorrücken umsetzen.

24:14 Ansonsten ist das im Wesentlichen wie in dem Beispiel gezeigt, aber die Zeit hat gezeigt, weil dieser Algorithmus so viel verwendet wurde, wurde sozusagen alle möglichen Fehler mal gemacht und auch in produktivem Code deployed. Falls Sie irgendwann in die Verlegenheit kommen sollten, so ein Partitionieren selbst bauen zu müssen, weil sie es irgendwo verändern müssen, wie auch immer, ähm dann machen sie nicht den Fehler, alle Fehler noch mal zu machen, sondern nehmen Sie im Wesentlichen diesen Code. Ähm, der hat viele gute Eigenschaften, die subtil sind. Ich werde dazu noch ein bisschen was sagen. Ähm, aber die sind sozusagen hier alle erfüllt. Die Zeit hat sozusagen sich ähm auf diese diese Implementierung eingeschossen als eine, die alle ähm guten Eigenschaften kombiniert. Vermeiden Sie das Rad neu zu erfinden.

25:05 Ähm ganz kurz ein zwei Kommentare noch dazu, die wichtig sind. Wir haben jetzt hier anders als vorhin nicht fest das linkeste Element als Pivot gewählt, sondern es gibt hier noch so einen Aufruf, über den wir dann nächste Woche im Detail sprechen werden, wie wir dieses Pivotelement wählen. Was hier dann passiert ist, dass dieses Choose Pivot uns einen Index zurückgibt und wir tauschen es dann an die linke Position. Also für den Rest hier können wir doch wieder so tun, als würden wir immer das linkeste Element als Pivot wählen. Aber wir haben durch diesen Swap vorher sichergestellt, dass das ein wohlgewähltes Element ist und nicht einfach, was da am linken Rand schon stand. Und ähm hier gibt's diese Invariante, die man auch im Beispiel vielleicht hätte sehen können. Ich habe immer diese zwei Zeiger, die den unbekannten Bereich vorstoßen. Alles links von Ist kleiner, alles rechts von J ist größer. Und wenn sich dieser Bereich hier in der Mitte äh aufgelöst hat, dann bin ich fertig.

26:07 Wenn Sie es interessiert, lesen Sie über die Subtilitätten hier. müssen sie von mir aus nicht wissen. Ähm werden wir im Detail äh nicht drauf eingehen, vielleicht ein paar Sachen in Übungen noch aufgreifen, aber für den Moment belassen wir es dabei. Partitionieren können wir in Place machen. Wir brauchen keinen Zusatzspeicher und es ist auch relativ effizient. Das läuft über jedes Element einmal drüber. Damit haben wir eine Quicksort Implementierung, die so erstmal auch vollständig ist.