Video 7-2: Primitive Sortieralgorithmen

0:03 Im nächsten Abschnitt schauen wir uns ein paar Algorithmen an, die man vielleicht so in mehr oder weniger der Form nach ein bisschen Nachdenken immer findet, wenn man einfach sich mal irgendwo hinsetzt und überlegt, wie könnte ich denn systematisch eine Liste von Objekten sortieren?

0:22 Da die nahliegend sind, ähm möchte ich die auf jeden Fall als erstes auch diskutieren und wir werden dann insbesondere auch sehen, dass man in der sehr allgemeinen Weise was über all diese Verfahren sagen kann. Ein kleiner Spoiler ist, es wird eher was Negatives sein, aber dazu später. Also sortieren ist das klassische Beispiel, wo es äh zwar nur eine Aufgabe gibt, aber ganz viele Möglichkeiten, sie zu lösen. Was umso wichtiger macht, dass wir eine Methodik jetzt gelernt haben, mit der wir verschiedene Lösungen vergleichen können. Das werden wir also auch gründlich hier tun. Ähm, die Verfahren selbst sind relativ einfach. Wenn Sie noch ein bisschen mehr Details dazu lesen wollen, dann können Sie in die beiden Lehrbücher reinschauen. Ich habe mich hier relativ kurz gehalten, weil es auch nicht so richtig komplizierte ähm nicht so richtig viel dazu zu sagen gibt, wenn man wenn man so möchte.

1:14 Ähm viele der Verfahren haben eine Äquivalenz, Entsprechung, wenn man Dinge in der realen Welt sortiert im kleinen Maßstab manuell. Und was wir sehen werden, ist, dass die die Arten von Operationen, die bequem umzusetzen sind, immer auch beeinflussen, welche Algorithmen nahliegend oder auch schnell sind. Wer wir gleich konkreter sehen. Ähm an dieser Stelle möchte ich für den für den folgenden Code zumindest immer diese Vereinbarung hier treffen, dass wir uns zwei kleine Hilfsmethoden schreiben. Eine macht einfach den Vergleich ähm Bau echt kleiner W und gibt uns das Ergebnis als Booli zurück. Das macht natürlich nichts anderes als diese compare to Methode aufzurufen, wenn das comparable ist. In diesem Fall mit dem Comparator muss ich die Comparefunktion von diesem Comparator aufrufen. Und sie erinnern sich an die Semantik mit den drei möglichen Fällen. Wir interessieren uns hier für den echt kleiner Fall. Das wird für die ganzen Algorithmen ausreichen. Ähm im Allgemeinen können die äh auch andere Vergleiche realisieren. Und das zweite, was wir benötigen, ist Elemente vertauschen.

2:31 Wir hatten kurz drüber gesprochen, dass wir im Wesentlichen äh als Eingabe ein Array bekommen. Hatte ich jetzt in der Wiederholung nicht noch mal erwähnt. War glaube ich ganz am Anfang in den Folien. Also, wir werden immer als Eingabe ein Array bekommen, dass wir einfach umsortieren wollen. Dementsprechend ist das einzige, was man sozusagen tun kann, ein solcher eine Vertauschung von zwei Positionen. Ich könnte natürlich auch mehrere Elemente auf einmal in die Hand nehmen und die in der anderen Reihenfolge zurück schreiben. Das kann ich aber immer auch als Swaps ausdrücken und die Effizienz ist ähnlich. Deswegen für die Verfahren, die jetzt kommen, ist das die einfache Funktion. Das heißt, wir haben zwei Positionen, I und J. Wir möchten die Elemente an der Stelle tauschen. Sie kennen das natürlich, aber nur noch mal ähm kurz erwähnt, wie macht man das? Man schreibt eines der Elemente irgendwo in eine temporäre Variable, dann kann man den Wert überschreiben mit dem anderen und dann kann ich das andere Element überschreiben mit dem gemerkten Wert aus der temporären Variable.

3:40 Dann schauen wir uns den, wie ich finde, nah linksen Algorithmus an. Wir möchten sortieren in einer sortierten Folge und auch hier ähm soll ich vielleicht die Bildchen kurz erklären. Wir werden derartige Animation dann auch öfter so verwenden. Die Höhe von dem Balken soll angeben, wie groß dieser Wert ist. Also eigentlich steht hier unten drunter ein Array. Ja, und das hat Einträge an der Position 0 und 1 und 2 und so weiter. Äh und die Höhe von diesem Balken ist eben eine Darstellung von dem Zahlenwert oder dem könnte ja auch ein allgemeines Objekt sein. Sagen wir mal, wir sortieren ähm Zahlen. Dann ist diese Höhe von dem Balken einfach die der Wert der Zahl. Äh das heißt natürlich, dass Sortieren so eine so eine grafische Komponente hat. Wir möchten, dass diese Balken von links nach rechts immer größer werden. Nachdem ich mit sortieren fertig bin, ist offensichtlich an der linkesten Stelle das kleinste Element. Wir hatten gesagt, wir wollen aufsteigend sortieren. Dementsprechend ist es so rum.

4:41 Sie könnten allgemein natürlich auch andersrum sortieren, aber bei uns ist immer aufsteigend. Also das kleinste Element soll hier vorne stehen. Dann lassen Sie uns das doch zum Maßstab unseren Algorithmus machen. Wir finden das kleinste Element in der Liste und tauschen es mit der ersten Position. Und sobald ich das getan habe, habe ich das erste Element dorthin gebracht, wo es hin muss, das kleinste Element. Und der Rest der Liste kann ich mit dem gleichen Verfahren weiter sortieren. Und das erste Element ist aus der Betrachtung ausgeschlossen.

5:19 Da ich die Idee einfach genug fand, so in Worten kurz zu beschreiben, habe ich das gar nicht als Pseudocode aufgeschrieben oder die Idee noch mal formuliert, genauer als es hier steht. Äh, in Code könnte man es so ausdrücken. Wir haben unser Array und eine Schleife über das Array gibt mir an, bis habe ich schon die minimal nach vorne gebracht. Also, der Präfix wird auch gleich da stehen, aber damit wir den Code hier kurz erklären können. Der der Präfix der ersten I-Elemente sehen Sie sich an die Schreibweise. Das heißt 0 ist inklusive. Index I ist exklusive, also die Länge von diesem Bereich 0 bis I exklusive sind genau ielemente.

6:11 Die Idee wird sein, dass dieses I angibt, wie viele Elemente sind schon sortiert am Anfang der Liste? Am Anfang ist das null, das ist auch korrekt, denn wir haben ja noch nichts getan. Und am Ende soll es n sein, dann sind wir hoffentlich fertig. Und wie kommen wir von einem I zum nächsten?

6:33 Für diesen Schritt vielleicht mit deutschen Anführungszeichen ähm finde ich das nächste Minimum im äh verbliebenen Bereich. Also, wenn ich bis hierhin schon sortiert habe, dann ist der verbliebene Bereich das hier. Das heißt, ich habe eine Schleife, die mit einem zweiten Index J über diesen verbliebenen Bereich einmal läuft und wir merken uns, was war der kleinste Wert, den wir in dieser Iteration gesehen haben und was war die Position dieses kleinsten Wertes, denn wir müssen ja den für die Vertauschung die Position kennen. Für jeder dieser Stellen hier, für jedes J ich ein bisschen doof, weil das ja jetzt hier schon sortiert ist. Das sieht man nicht viel. Ah, es geht ja früh los hier mit Technikproblemen.

7:19 [räuspern] Jedes J machen wir den Vergleich. Wiees J vergleichen wir den Wert an dieser Stelle J mit dem bisherigen Minimum. Wenn das neue der neue Wert noch kleiner ist, dann merken wir uns den neuen Wert stattdessen. Das heißt, am Ende dieser Schleife sagen an dieser Stelle ist das A-POS das kleinste Element aus diesem restlichen Bereich. Ich schreib es mal ein bisschen lapsiger. So, also von i + 1 angefangen, na ja, wir haben das i mit mitgeprüft, also die Minimum mit drin, also I bis N.

8:17 Das soll einfach heißen, das kleinste Element, was in diesem Teile Array vorkommt, das ist dasjenige, das hier an dieser Position steht. Und dann mache ich eine Vertauschung an Position I. Dann steht das Minimum hier an dieser Stelle. Äh in diesem Beispiel ist es schon sortiert, das sieht man nichts. Und dann kann ich i1 größer machen und erhalte diese Eigenschaft, die ist dann auch für den nächst größeren Wert von I wiederhergestellt. [räuspern] Was ich Ihnen hier informell erklärt habe, ist sowas wie eine Schleifeninvariante. Das kann man verwenden, um formal zu beweisen, dass der Code das tut, was wir behaupten. Wenn wir hier in der Vorlesung nicht als formalen Beweis machen, das führt uns zu weit. äh könnt man könnte das in der Software Verifikation machen. Ähm ich verwende das aber trotzdem gerne, um so ein bisschen die Plausibilitätsargumente zu strukturieren. Warum macht der Code das, was er tut? Kann man mit mit so ein bisschen dieser Art von Formulierung über Invarianten meistens prägnanter machen und dann sind sie auch schon auf dem halben Weg zu einem formalen Korrektheitsbeweis.

9:28 In Kurzbaum ähm steht das noch mal hier die Innvariante nur für die äußerste Schleife. Die spannendere Frage ist vielleicht an dieser Stelle, sie hätten wir vielleicht auch ohne jetzt diese lange Rede geglaubt, dass der Code das Richtige tut, aber wie schnell ist das jetzt oder wie gut ist dieser Algorithmus? Und dafür können wir den analysieren. Das haben wir ähm fleißig geübt. Ähm wir zählen dafür gucken.

9:57 Zählen wir hier mal nur die Anzahl Vergleiche. Ähm, denn das andere, was ja auch Sinn machen könnte, wären die Swaps. Das haben wir aber nur hier außen. Welche können wir gleich noch zu kommen, das sind viel weniger.

10:17 die Anzahlvergleiche, die wir hier brauchen. Wenn ich das Mikro irgendwann vergessen sollte, erinnern Sie mich einfach. Wo machen wir Vergleiche genau an dieser Stelle? Wie oft kommen wir an diese Stelle? Also hier diesen Teil, da machen wir eine Konstante Anzahl an Vergleichen, Konstanteekosten. Dann haben wir eine Zählschleife. Haben wir jetzt schon einige Male gemacht.

11:14 Statt jetzt präzise anzugeben, wie oft die ausgeführt wird, mache ich mir das Leben etwas einfacher. Dann muss ich nicht genau gucken. Ungefähr n- j viele äh Iteration hier, weil ich bei n aufhöre und bei sorry J ist quatsch i und bei i anfange. +-1 verschwindet angenehmerweise in dieser Tiltenotation.

11:40 Dann haben wir hier noch mal ähm konstante Extra Arbeit, die aber keine Vergleiche macht. Das heißt, was ich hier ähm für diesen Bereich mit der Schleife angegeben habe, schließt auch diesen Teil mit ein und schließt auch hier diesen Swap mit ein. Das heißt, der ganze Schleifenrumpf der äußeren Schleife hat Kosten n- I.

12:00 Das heißt, für die ganze äußere Schleife muss ich die altbekannte Summe lösen. I von 0 bis N, weil jetzt präzise sein wollen, machen wir das -1 n- I. Dann habe ich eine Tilde Asymptotik für die Gesamtlaufzeit und vielleicht kennen Sie das jetzt langsam auch im Schlaf. Wir summieren rückwärts, dann haben wir die kleine Gausformel und die Lösung davon war ungefähr n quadrat halbe.

12:32 Streng genommen wäre hier, man muss den letzten Wert nehmen mal sich selbst + 1 und dann durch 2. Also exaktes Ergebnis wäre n mal n - 1 dur 2. N quadrat halbe als Tilte Approximation reicht uns. Das ist sehr präzise als Abschätzung. Okay, das noch mal im gleichen Stil, wie wir das exzessiv geübt haben. Fast schon wir haben es fleißig geübt, sagen wir mal. Wenn man nur die Anzahl Swops zählen würde, ist ja auch eine interessante Frage, wie viel muss ich vertauschen? Dann sieht's hier besser aus. Ich habe nur hier diese konstanten Kosten in dieser ganzen Schleife von einem Swap an dieser Stelle.

13:18 Lassen Sie mich hier auch eine ein draus machen, dann ähm ergibt das ja auch mehr Sinn mit der Konstante. Wir haben ein Swap hier, das heißt, wir haben ein Swap in der ganzen Schleife hier außen. Für Swaps hätte ich also nur diese Summe 0 bis n- I über die Zahl 1, das heißt etwa n. Also, wenn Sie das vergleichen hier, das wächst quadratisch, das wächst nur linear. Die Anzahl Swaps hier ist viel viel kleiner. Als dominante Operation müssen wir hier die Vergleiche uns anschauen.

13:56 In aller Kürze ist es auf der Folie hier nur einfach als Ergebnis erwähnt. Ähm haben wir kurz kurz diskutiert, werden sie in den Übungen ja auch noch mal ein bisschen ähm diesmal ähm anhand von konkreten Code analysieren. Das ist unser erstes Sortierverfahren, Selection Sort. Jetzt wissen Sie noch nicht, womit wir es vergleichen. Ähm, aber eine interessante Eigenschaft von diesem Algorithmus ist ja zumindest mal, dass er äh immer die gleiche Anzahl an Vergleichen und Swaps macht.

14:31 In der ganzen Analyse, deswegen habe ich sie noch mal ein bisschen im Detail gemacht, haben wir nirgends irgendeine Eigenschaft der Eingabe gebraucht, abgesehen von der Gesamtlänge. Das heißt, dieser Algorithmus ist von seinen Kosten her vollkommen Datenunabhängig. Das kann eine ganz gute Sache sein, weil dann äh man man keinen Worst Case hat, der irgendwie schlimmer ist. Es kann aber auch heißen, dass jede Eingabe in Worst Case ist, je nach Sichtweise.

15:02 Schauen wir uns mal an, ob wir das irgendwie besser hinbekommen. Ein erster Versuch ähm ist ein Algorithmus, den den man vielleicht einfach nur äh wegen der Memes kennen muss. Die einfachste Variante von diesem Algorithmus Bubble Sort würde ich so beschreiben. Wir laufen immer wieder durch die Liste und schauen uns zwei benachbarte Elemente an. Und wenn eins davon größer ist, dann hat das mehr Luftblasen und steigt dem nach oben. Das heißt, in diesem Fall würde ich diese zwei vertauschen, sodass dann irgendwann am Ende äh das leichteste Element ganz oben ist. Verzeigen Sie mir hier, dass für die Bildsprache sozusagen die Bedeutung umgekehrt ist. Der der breiteste Balken ist am Ende der in Position null. Das hat zu malen besser geklappt, aber eigentlich ähm na ich habe irgendwie gedacht an an Dinge, die schwimmen und dann ist äh ein größeres Objekt schwimmt besser. Müssten wir sozusagen die Definition der Länge der Balken negieren.

16:09 Was hier noch nicht so ganz klar ausgedrückt ist, ist wie machen wir das jetzt systematisch? Und ähm die einfachste Idee von Bubblesort ist, wir lassen einmal so diese Beobachtung da hochlaufen. Dabei verfolgen wir immer ein kleinstes Element. Also Stück für Stück wandert das nach oben und dann habe ich nach einem Durchgang das kleinste Element an die oberste Position gebracht, denn es egal wo es vorher war, sobald ich mit meiner Betrachtung an diesem Element vorbeikomme, muss es mit aufsteigen und sobald ich das Minimum einmal gefunden habe, wird es in jedem Fall immer weiter aufsteigen. Das macht also jedes Mal den den Vergleich den die Vertauschung mit nach einmal von komplett unten bis oben laufen mit jeweils vertauschen ist das Minimum an der obersten Stelle und ich kann es wieder genau wie bei Selection Sort dann aus der Betrachtung ausschließen und mach noch mal einen zweiten Durchlauf, wo ich ein Element vor eher stoppen kann.

17:15 Als Code kann man das auch ähm kompakt ausdrücken und vielleicht lassen Sie mich, bevor wir den Code im Detail lesen, einmal Animation dazu laufen. Ich werde das ein bisschen hin und her wechseln. In dem Fall habe ich eine eine bekannte Webseite bemüht, Visualgo, die alle möglichen Algorithmen analys äh visualisieren und oft auch das sehr kleinschrittig anzeigen. Und da gibt's eben diesen Teil zu Selection Sord. Wir wollen aber den Bubble Sord an der Stelle.

17:53 Also, wir vergleichen immer das größere wandert wandert nach rechts. Das machen wir solange, bis hier ähm das größte Element ganz drüben ist und dann fangen wir wieder von vorne an und so weiter und so fort. Äh, lassen Sie mich an der Stelle mal abbrechen. Wir machen das gleich noch mal in Ruhe. Ähm, in Code sieht der Algorithmus dann so aus. Ich habe eine äußere Schleife, das sind die Durchgänge und ich habe eine innere Schleife, die mir sagt, von wo bin ich immer mal aktuell mit meinem mit meinem Bubbelschritt. Und ein Bubbelschritt vergleicht zwei benachbarte Elemente, wie z.B. hier die hier. Und wenn das weiter unten befindliche Element kleiner ist, dann vertausch es.

18:42 Warum funktioniert das überhaupt, wenn ich das in irgendeiner systematischen Reihenfolge mache, ohne mir groß Gedanken zu machen, dass ähm dass wir hier womöglich nicht genug über die Eingabe laufen. Zumindest ähm werde ich mit jeder Vertauschung etwas sortier mache einen ein Vertauschungsschritt, der das Gegenteil bewirkt. Das heißt, äh nach jedem nach jedem Schritt werde ich ein bisschen sortierter und kann nach einer Iteration der äußeren Schleife das erste Element ausschließen. Ähm hatte ich eben schon gesagt.

19:21 Und nach äh dem gleichen nach der gleichen Analyse wie ebenfast kriegen wir auch die Anzahlvergleiche mit dem gleichen Ergebnis. Lass mich hier nur kurz machen.

19:33 Wir haben immer einen Vergleich hier drin. Dann haben wir so eine doppelte Schleife, wie wir sie schon x mal hatten. Das ist wieder die das gleiche Muster. Wir summieren j von diesmal rückwärts von n etwa n bis I. Also hier haben wir wieder n - I durchläufe jeder jeweils mit Kosten 1. Das heißt, dieser ganze Teil der inneren Schleife kostet etwa n - i.

20:01 Demnach ist die äußere Schleife wieder die gleiche Summe. Warum auch immer ich hier kleiner = n -2 statt echt kleiner n -1 geschrieben habe, wie auf der vorigen Folie. Ähm ist ist mir jetzt auch nicht mehr klar. Ergebnis ist das gleiche. Also wir brauchen genauso viele Vergleiche wie das Selection Sort.

20:31 um zu motivieren, was wir als nächstes hier tun können. Ähm lassen Sie uns mal ein kleines Beispiel von Hand sortieren und wir führen den Algorithmus streng so wie er in dem Code steht aus. Okay, das heißt insbesondere, ich will mir irgendwo mein aktuelles I und J merken.

21:07 Wir fangen mal an mit i = 0. Das ist der Anfang hier. dann ist jn- 1. Das heißt in unserem Fall ist ja n 6, dementsprechend ist j 5 konkrete Zahlen.

21:23 Das heißt, wir sind hier in Position 5. Wir schauen uns die beiden Elemente an und ich frage mich, ist das untere kleiner als das größe als das äh höhere? Und in jeden Fall ist es so, sie erinnern sich mehr Luftblasen heißt kleiner. Ich steig nach oben, schwimmt besser. Das heißt, in dem Fall würde ich die beiden vertauschen.

21:45 Dann habe ich diesen Schritt abgeschlossen und würde mein J um ein kleiner machen. Na, hier auf vier gesetzt. Das heißt, ich schaue mir diese beiden Elemente an. Da ist das untere schon kleiner. Das heißt, das bleibt wie es ist. Und ich gehe zum nächsten Element. Dann ist J3, ne? Ich schaue mir diese beiden an. Diesem Fall ist das Untere wieder größer. Das heißt, wir vertauschen die einmal Platz machen. Tauschen hierhin und ich gehe wieder eins weiter. Den hätte ich mir äh sparen können. J ist jetzt 2. Ich schaue mir die beiden an. Ich muss wieder vertauschen, denn das hier ist ja größer, leichter.

22:41 Muss mir antrainieren zu sagen, dass das hier kleiner ist in der Sortierordnung, obwohl es länger ist. Mehr mehr Blasen. Gut. Ähm, dann haben wir J = 1 und wir vergleichen die beiden auch. Da ist wieder das hier größer. Wie sie ja sicherlich schon erkannt haben, haben wir hier das Element, was ganz nach oben muss. Dementsprechend muss das ja immer weiter aufsteigen. Und sobald J i + 1 erreicht hat, also 1, ist diese Iteration zu Ende. Okay, das war die Iteration mit I = 0.

23:24 Jetzt setzen wir i auf 1. Mit J fangen wir auf n - 1 wieder an, wieder bei der 5. Und damit wir so ein bisschen die Historie haben, kopiere ich hier mal meine Elemente.

23:35 Äh könnte mit Platz etwas knapp werden, aber ich schaue mal. Zweifel müssen wir nachher ein bisschen schummeln. Jetzt machen wir das gleiche noch mal. Ähm fangen bei den unteren beiden an. Die sind schon richtig. Bra ich nicht mal nichts machen.

23:56 Die sind auch schon richtig. Wollen wir auch nichts machen. Die da sind auch schon richtig. Ah, cool. Brauchen wir nichts machen. Hier passiert noch mal was. Da ist jetzt tatsächlich das hier größer. Das wandert hierhin. Ich meine Vertauschung gemacht. Dann kommt die 1. Äh nein, brauche ich nicht mehr machen. Ich bin ja bei i + 1 schon angekommen. Das heißt, ich weiß schon, dass die oberen beiten richtig sind, denn das eine war ja das das absolut kleinste, dass wir komplett hoch gebappelt hatten. Das brauche ich nicht noch mal angucken. Damit ist hier auch die Iteration für i = 1 zu Ende.

24:48 [räuspern] Wir könnten natürlich einfach auf der nächsten Seite weitermachen, falls es nicht klappt. will sie auch gar nicht bewusst langweilen, nur so ein bisschen, damit Sie ein Gefühl dafür haben, wie unfassbar nervig langsam dieser Algorithmus ist. Ähm, das liegt nicht nur daran, dass man dass ich beim malen langsam bin, aber es hat sozusagen einen didaktischen Wert. Bleiben Sie noch kurz bei mir. Wir haben hier die fünf wieder. Da passiert nichts. Dann vergleichen wir die vier. Da passiert auch nichts. Ja, wir sehen schon äh da passiert erst hier wieder was, wenn ich bei der drei angekommen bin. Jetzt ist tatsächlich das untere wieder mal größer und ich muss tauschen und dann bin ich fertig. Ähm, ich [räuspern] weiß ja schon, dass das hier das Minimum aus dem vorigen Schritt war. Das heißt, hier höre ich auf jeden Fall auf. Ich habe ihn dann wieder bei i + 1 angekommen.

25:45 So, und jetzt macht unser Algorithmus, ne? Den Strich hätte ich äh behalten wollen. M jetzt könnte ich entweder neue Seite anfangen oder wir schummeln ein bisschen.

26:02 Äh, dass da unten drunter noch die Elemente sind, stört jetzt so ein klein wenig. Da könnte man natürlich noch mehr schummeln. Jetzt muss ich das nur irgendwie dazu bekommen, hinter den Dingern zu sein. Wä schon schummeln dann richtig oder?

26:34 Okay, habe ich das Ding verloren. Neuer Versuch. Okay, vergessen es. Wir lassen wir lassen die Schummelei an der Stelle. Ähm, sie schlafen mir eh schon ein, denn der Algorithmus macht jetzt Stur das gleiche noch mal. Ich fange wieder bei fünf an. Ich weiß, ich muss nicht höher als hierhin gehen, aber ich vergleiche Stuh noch mal die beiden und stelle fest, die sind noch in der reich richtigen Reihenfolge. Und ich vergleiche Stuh die beiden und stelle fest, sie sind noch mal in der richtigen Reihenfolge. Und jetzt würden wir sogar noch einen Schritt weitergehen. Jetzt ist äh das I bei 4 angekommen. Dann würde ich den Strich hier einziehen und ich würde noch mal diesen dusligen Vergleich machen, als ob der diesmal was anderes ergeben würde. Der Algorithmus macht ähm weiteren Aufwand an der Stelle, wo man als Beobachter, wenn man den von Hand ausführt, es fast nicht erträgt, weil man es schon sieht, dass es unnötig ist.

27:47 Aber wie können wir das ein bisschen ähm systematisch fassen, was genau das äh verschwenderische hier war? Der Punkt ist, dass man, wenn man mit den Elementen aufsteigt, ab einem gewissen Punkt, wenn sich nichts mehr ändert, auch beim nächsten Mal keine Änderung mehr haben wird. Also konkreter und für die Formulierung muss man sich vielleicht ein bisschen bisschen ähm mit dem Algorithmus im Detail beschäftigen. Das kann ich Ihnen jetzt leider nur vorwegnehmen, sonst kommen wir nicht nicht schnell genug voran. äh wenn in der letzten Vertauschung ab einem bestimmten Punkt, wenn wenn in der letzten Iteration die letzte Vertauschung auf einer bestimmten Höhe passiert ist, z.B. hier und danach wurde nichts mehr vertauscht. Also hier hatten wir eine Vertauschung und hier keine Swaps, während der Algorithmus weiter nach oben gewandert ist. Dann ist auch in den nächsten Iterationen hier nichts mehr zu erwarten, denn dieser Präfix, der das Algorithm das Array sie nennt sich, wir nummerieren von oben.

29:05 T ist der Teil, der nicht mehr dazu gehört. T -1 gehört noch dazu. Dann enthält dieser Präfix der ersten oberen T-Elemente schon die t kleinsten und auch schon sortiert. Das heißt, die muss ich mir nicht noch mal angucken. Wir hatten das ausgenutzt, dass es nach einem kompletten Durchlauf immer t mindestens um eins größer wird. Tatsächlich kann T aber um mehr als eins größer werden, je nach je nach der Eingabe. Und diese etwas verfeinerte Variante von Bubblesort, die kann man so in Java implementieren. Wir haben uns wir merken uns diesen Wert T. Wann wurde das letzte was ist die letzte Position? und der es noch eine Vertauschung gab und solange ähm das nicht keine mehr war, also wir haben so ein so ein Abbruchwert. Ähm das T hat hat die die schönere Bedeutung, dass die kleinsten Elemente in den ersten T-Pition sind. Ähm, solange das nicht alle sind, setze ich es erstmal auf auf N und werde es dann äh runtersetzen, wenn ich wenn ich neue Evidenz finde. Der Rest vom Code ist wie gehabt, aber ich habe jetzt, wenn ich eine Vertauschung mache, den Wert von T auf das aktuelle J gesetzt.

30:20 Sie sehen ja, ähm die Schleife von J läuft rückwärts. Wir laufen von den großen Werten unten zu den kleinen nach oben. Das heißt, der letzte Wert, der hier überschrieben wird, ist der kleinste. Ist der am weitesten oben gelegene.

30:37 Der verfeinerte Algorithmus hat also diese Invariante, die aus dieser Beobachtung folgt. Und ähm wir werden uns das einfach mal in einem Beispiel anschauen. Äh, was ich Ihnen vorhin gezeigt habe, ist tatsächlich auch dieser äh verbesserte Algorithmus. Der hat auch genau das T ist im Wesentlichen hier dieses ähm dieser längere Name.

31:01 Und wenn wir den hier noch mal laufen lassen, dann sehen Sie, was da passiert. Jetzt ist die 39 als größtes Element schon raus. War mal geben wir mal ein bisschen mehr Gas.

31:29 Noch ein bisschen mehr Gas. So, an dieser Stelle, stopp, stopp, stopp, stopp. [gelächter] An dieser Stelle haben Sie gemerkt, der Algorithmus hat jetzt festgestellt, dass er keine Vertauschung mehr gemacht hat und ist deshalb schon fertig. Ich war ein bisschen zu langsam mit wieder auf langsam stellen, aber können Sie sich auch in Ruhe noch mal anschauen. Äh, das Ding gibt's eh online. Ähm, was ich auch noch vorbereitet habe, ist eine Animation von Bubblesort mit mehreren verschiedenen Eingaben, die ein bisschen zeigt, dass es von den Daten abhängt, was da passiert.

32:11 Also ähm ähnliche Art, die die Dinger zu malen. Hier ist eine Eingabe, die im Wesentlichen zufällig ist. Man sieht es vielleicht, wenn man das noch mal äh refresht, ein bisschen deutlicher. Das linke wechselt jedes Mal komplett. Das sind einfach zufällige Zahlen. Das hier ist fast schon sortiert. Das sind nur so ein paar Elemente an der falschen Stelle. Ähm, der letzte Teil ist für den Moment noch nicht relevant. Das wird später spannender. Und hier haben wir eine Eingabe, die komplett falsch rumsortiert ist. Und wenn wir den Bubblesort hier starten, ich ma erstmal langsamer, dann sehen Sie hier bei den Random, da ging es weit nach oben. Während der nearly sorted ist schon fertig. Also machen wir vielleicht noch mal äh schauen Sie mal auf den Teil hier besser.

33:04 Wo war die letzte Vertauschung? Hier, wenn wir noch eine brauchen. Das heißt, die obersten Elemente muss ich mir jetzt gar nicht mehr angucken und das rote stoppt auch schon hier. Und jetzt hat er ganz gestoppt, weil in dem Durchlauf hier gar keine Vertauschung mehr passiert sind. Offensichtlich brauchen auf anderen Eingaben äh braucht dieser Algorithmus länger. Auf den zufälligen hier ist immer noch am Werkeln und bei den komplett falsch rumsortierten sieht's noch schlimmer aus. Da ist noch gar nicht viel passiert und ich muss noch hier eine ganze Menge an Vertauschung machen. Okay, also hängt einfach von den Daten ab und das sieht man ganz schön in dieser Gegenüberstellung.

33:48 Okay, das war das war der Bubblesort mit der leichten Verbesserung. Ähm, wie gut es jetzt genau funktioniert, dazu werde ich noch was sagen. Ich möchte aber zuerst noch den dritten üblichen Algorithmus vorstellen, den man manchmal als als die Kartenspieler Methode werd Guard gespielt oder sowas, was man noch mehr Karten auf der Hand hat. Äh, eine übliche Methode ist, man nimmt eine Karte nach der anderen auf die Hand und fügt die an der passenden Stelle in die Hand ein, die man schon sortiert hat. Das passiert ist halt insbesondere dann bequem, wenn man eh die Karten so nach und nach bekommt, ausgeteilt bekommt.

34:24 Äh auch das können wir in einem Array machen. Wir haben also ein Präfix vom Array. Das ist die Hand. Das ist schon sortiert. Und jetzt kommt ein neues Element hier dazu und für das muss ich jetzt die passende Stelle finden, wo es hin muss. In dem Fall hier.

34:49 Und äh als Kartenspieler würde ich jetzt einfach die Hand da ein bisschen auffächern, die Karte reinstecken. Das kann ich in dem Array aber nicht machen. In dem Array muss ich jetzt diesen Teil, der da bisher ist, um eine Position verschieben nach rechts und dann kann ich dieses Element hierhin einfügen. Das heißt, konzeptionell hat man hier viel Arbeit durch das Verschieben, selbst wenn man schon weiß, wo man hin möchte mit der neu mit dem neuen Element, mit der neuen Karte.

35:20 Im Code sieht es sehr, sehr kompakt und harmlos aus, ähm weil man in dieser Schleife die ganzen äh Dinge zusammen machen kann. Also, wir haben eine äußere Schleife, die im Wesentlichen sagt, wie groß ist meine Hand schon?

35:46 Als Innvariante wird immer dieser erste Teil äh schon sortiert sein, aber sortiert bedeutet hier unter den Elementen, die da drin sind, sind sie sortiert. Es könnte noch kleinere Elemente geben, die wir noch nicht gesehen haben. Die kommen erst noch weiter weiter rechts im Array.

36:05 Also mit jedem Schritt mache ich meine Hand um eins größer. Das heißt, ich schaue mir die nächste Position an. Hand geht ja bis exklusive I. Ich mache die runde Klammer mal etwas deutlicher.

36:16 Und äh J fängt bei der Position I an. Noch mal mein Bild von eben. Hier ist die Hand, da ist i - 1. Das ist die neue Karte, die ich einfügen möchte, das neue Element. Jetzt frage ich mich, indem J hier anfängt, ist äh bin ich noch nicht am linken Rand. Okay, das ist der eine der eine Abfrage. Und das andere ist, ist das J kleiner als was links davon steht? Wenn ja, dann muss ich diese beiden Elemente vertauschen und ich mach sozusagen dieses Block verschieben, was ich hier als als ein Bild gemalt hatte. Das mache ich Stück für Stück, Element für Element. Ich lass dieses dieses neue Element hier Stück für Stück in die sortierte Eingabe reinversickern, bis es an der Stelle ist, wo es bleiben kann. Und diese Stelle, wo es bleiben kann, die erkenne ich, wenn der linke Nachbar nicht immer noch größer ist.

37:17 Das ist alles. Ähm, weiß nicht, ob wir die uns die Animation an der Stelle vielleicht erstmal sparen. Die können Sie sich auch noch anschauen, wenn Sie mögen. Da gibt's dann den entsprechenden Code und sie können sich beliebige Beispiele anschauen. Äh, Invariante hatte ich schon erwähnt, das ist die Hand. Ähm, für die Analyse können wir zumindest eine obere Schranke angeben nach genau der gleichen Analyse wie vorhin. Ähm, sowohl die Anzahl Vergleiche als auch die Anzahl Swaps, die sind ja im Prinzip gepaart. Ich mache so eine Vertauschung immer direkt nach einem Vergleich und ich mache höchstens mal noch ähm einen Vergleich extra, wo dann der Abbruch passiert. Also, ich mache ein bisschen pro Element mache ich einen Vergleich mehr als ich Vertauschungen habe, aber um und bei sind das gleich viele, wenn man nur auf die führenden Terme schaut. Also, es ist hier ähm im Wesentlichen ein plus n, aber wir ignorieren das, weil uns die Details auf dem Level gar nicht interessieren. Das ist eh nur eine obere Schranke, die davon ausgeht, dass ich eben diesen diesen äh Vergleich hier jedes Mal so oft machen muss, bis diese erste Bedingung fehlschlägt. Also jedes Mal, wenn ich einfüge, musste ich die komplette Hand nach links reintauschen.

38:38 Können sich ja schon mal überlegen, welche Art von Eingabe für diese obere Schranke hier dann zuständig ist oder welche dafür verantwortlich ist. Lassen Sie mich an der Stelle einstreuen, dass man mit dem Wissen von Montag das Finden der Einfügeposition verbessern könnte durch binäre Suche. Denn dieser linke Teil, in den wir das Element einfügen wollen, der ist ja sortiert, also kann ich binäre Suche verwenden. Damit kann ich die, das hat auch einen Namen, Binary Insertion Sult ist manchmal hilfreich. Ähm, das verbessert die Anzahlvergleiche massiv, aber es hilft in dem Fall nicht sehr viel, denn die Vertauschung muss ich trotzdem machen. Ich muss ja trotzdem mein Element in dieses komplett vollgeschriebene Array weiter vorne bringen und das geht nur, indem ich alle anderen Elemente um einen Schritt bewege. Das heißt, das lohnt sich dann, wenn wenn die Vergleiche ähm hilft, äh ist dann einen Gedankenwert, wenn die Vergleiche extrem teuer sind und die Bewegungen nicht. Aber für den üblichen Fall äh wie in Java ist es wenig hilfreich. Ja, ich ich kann ähm die Vertauschung damit nicht verbessern.

40:03 Was sie daran sehen, ähm bei Insertion Sort offensichtlich, weil diese Schleife nicht gleich oft lang läuft und bei dem verbesserten Bubble Sort, weil ich irgendwann früher aufhören kann. Beide sind äh Datenabhängig und wir hatten das für Bubblesort ja schon gesehen. Ich mache Ihnen einmal noch das Bild hierfür an.

40:21 Das sind jetzt wieder äh vielleicht ein bisschen langsamer die gleichen vier Typen von Eingaben und sie sehen, dass auch hier wieder ähm das fastsortierte sehr schnell fertig ist. Äh das zufällige ist irgendwo in der Mitte und die komplett rückwärts sortierte Eingabe ist halt genau die, für die dieser Worstce Case eintritt. Jedes Mal muss ich hier in der Hand komplett nach links tauschen, um das nächste Element einzufügen. Das ist eben das äh der maximale Aufwand. Und hier sieht man auch, das wird sozusagen je je mehr man vorankommt, desto langsamer und träger wird das, weil ja hier diese Distanz immer größer wird.

41:14 Aus dem Buch gibt es eine ganz hübsche Art, ähm zu malen, optisch hervorzuheben, was der Insertion Sort für Kosten hat. Ähm bisschen bisschen eigenwillig, wenn Sie mögen, aber ich find's sehr effektiv. Was hier gezeigt ist, sind die Iterationen. Also hier in jedem Schritt wird die Hand eins größer. Das sehen Sie an diesem dieser Diagonal, die markiert sozusagen bis wohin die Hand reicht, der sortierte Teil. Und was dann hier in Fett gedruckt ist oder in nicht ausgekraut, das ist die Vertauschungen. Und das rote Element hier ganz links ist das, dass wir äh eins über der Diagonalen finden wir das E und das wurde dann hier reinvertauscht, bis es an dieser Stelle gelandet ist. Was was Sie hier optisch sehen können, ist für so eine zufällige Eingabe, wie weit musste ich jeweils nach links zurücklaufen mit den Vertauschung, um das Element einzufügen. Und es gibt einem vielleicht so optisch ein bisschen ein Gefühl dafür, dass bei dieser Eingabe, na, so im Schnitt, wenn man mal so ganz grob drüber schielt, würde ich wahrscheinlich sagen, man hat so die Hälfte etwa immer, ne?

42:18 Das ist natürlich nicht ganz wahr. Manchmal muss ich weiterlaufen, manchmal konnte ich früher stoppen. Aber für so eine zufällige Eingabe ist es vielleicht plausibel zu erwarten, dass man etwa die Hälfte der Distanz in die Hand zurücklaufen muss.