Video 7-3: Analyse Primitive Sortierverfahren

0:02 Nachdem wir jetzt drei relativ nahliegende Algorithmen gesehen haben, die alle korrekt sortieren können, aber auch im Worst case mit quadratischer Laufzeit vielleicht noch nicht so bei zufriedenstellend sind, wollen wir uns jetzt ein bisschen die mathematische Analyse dazu anschauen, die interessanterweise ein sehr allgemeines Statement geben wird, was man auch als Hinweis interpretieren kann oder darf oder muss. äh wie man bessere Algorithmen designen muss, wenn sie besser sein sollen, muss man diesem Ratschlag letztlich folgen.

0:37 Ich habe sie gefragt, was ähm intuitiv ihr ihre Idee ist, welcher dieser Algorithmen vielleicht äh vielversprechender ist und es ist äh einigermaßen verte gleichmäßig verteilt über diese drei Algorithmen. Es ist ja auch schwer, also das sind ja auch alle drei schön. Ja, ich ich bin ich verstehe verstehe sie ja. Äh werden aber sehen, es man kann so ein bisschen was darüber sagen, was über rein ähm rein Bauchgefühl und Sympathie hinausgeht. Äh wenn jemand noch zu der Frage was abstimmen will, dann tun Sie es. Ich möchte sonst dann mal die Votes sperren, damit wir ähm das Bild so erhalten.

1:20 Wir haben gesehen, dass insbesondere Bubblesort und Insertion Sort auch Daten abhängig sind. Ähm was aber nicht unbedingt gut ist, das weiß man nicht so wirklich. Wir hatten ein paar äh Animationen gesehen, die im Wesentlichen wann immer ähm entweder Vergleiche oder Vertauschung passieren, so ein so ein äh den nächsten Frame zeigen. Und da konnte man ganz gut erkennen, dass für verschiedene Daten verschiedene Dinge passieren. Aber auch daraus allein ähm kann man natürlich höchstens eine Hypothese ableiten, die man dann irgendwie vielleicht versuchen kann zu beweisen. Für den Insertion Sort aus der Animation, aus dem Buch hatte ich ihn ja auch schon sowas angedeutet, was vielleicht äh eine Hypothese sein könnte. Äh, aber die Frage ist so ein bisschen, was was wollen wir überhaupt? Ähm, was ist überhaupt die konkrete Frage? Und die Slidofrage ist schon so ein bisschen ein Hinweis in die Richtung, in die ich hier gehen möchte, nämlich Worst Case war für alle drei Verfahren n quadratbe nach einem der Kostenmaße mindestens.

2:19 Das ist nicht besonders gut. Und da sind sie auch alle drei etwa gleich. Also lassen lass lassen Sie uns mal den Average Case versuchen zu berechnen, um ein Gefühl dafür zu kriegen, was für diese zufälligen Eingaben passieren sollte. Dafür müssen wir aber genau sagen, was heißt denn jetzt zufällig? Da hatte ich mich drum gedrückt, als ich die Bildchen, die Animation gezeigt habe, äh das genauer zu erklären. Das möchte ich hier nachholen. Ähm bisschen Notation dafür, die in der Informatik super üblich ist. Diese eckige Klammer n ist einfach ein Bereich an Integern von 1 bis n. Die Mathematiker würden das immer gerne so schreiben, weil wir das so oft benutzen, ist das einfach eine Abkürzung. Ähm, eine Permutation ist eine Abbildung, eine bijtive Abbildung, das ist wichtig, von diesen ersten n natürlichen Zahlen in diese Menge zurück. Muss bei der Btion ja so sein. Äh für die Informatiker schreiben wir aber, wenn wir eine Permutation angeben wollen, nicht irgendwie eine Tabelle mit äh Wert und dann Funktionswert, sondern wir listen einfach in der Reihenfolge von 1 bis n die die Funktionswerte auf.

3:29 Daraus kann man natürlich ablesen, was diese Funktion hier ist. Wir werden aber in der Regel das gleichsetzen. Also eine Folge von Zahlen, eine eine etwa äh umsortierte ähm Anordnung dieser ersten N inte Integer werden wir gleichsetzen mit der Permutation, die dahinter steht, die also diese Abbildung äh realisiert. Äh wenn Sie in den Beispielen glaube ich ohne Probleme sehen, z.B. ist diese sortierte Folge eben die Identitätsfunktion, die jedes Element auf sich selbst abbildet.

4:06 Ähm allgemein könnte man ähm für diese Permutation diverse Sachen definieren. Wir werden uns im Wesentlichen dieses hier anschauen und das ist einer dieser Fälle äh wo man, wenn man die richtige Definition hat, der Rest dann einfacher wird. Wie man aber auf diese richtige Definition kommt, das ist der clevere Teil, wo man irgendwie diesen Geistesblitz, den Geniestreich äh haben muss. Wir definieren für eine Permutation, dass ein ein Paar von Indic Inversion ist, wenn die Indizes sortiert sind, aber die Funktionswerte umgekehrt sortiert sind. Sprich, äh, wenn ich hier dieses Beispiel habe, also einmal als Tabelle aufgeschrieben, damit wir damit wir das vielleicht einmal hingeschrieben haben, als Funktion würde ich diese Permutation so schreiben wollen. Die 1 wird auf die 2 abgebildet, die 2 auf die 1, die 3 auf die 4 und die 4 auf die 3. Also ich schreibe hier diese Folge einfach hier unten in die Tabelle. Und es gibt genau zwei Inversionen, nämlich die ersten beiden Indiz. sind ein ist kleiner als 2, aber 2 ist größer als 1 und 3 und 4.

5:14 Das sind die zwei Inversionen in dieser Permutation. Alle anderen Paare von Indic äh sind korrekt sortiert. Okay, bleib geben Sie mir ein Moment. Äh wir kommen direkt zum Sortieren zurück, aber ein bisschen was ähm an Vorarbeit lohnt sich. Ähm, noch zwei Begriffe und dann gibt's eine intuimive Version, sich die zu merken. Äh, der erste Begriff ist, für eine Permutation kann man eine inverse Permutation definieren. Das einfach die Umkehrfunktion im mathematischen Sinn, da die Funktion Permutationen sind immer Buktionen, das heißt, die haben immer eine eindeutige Umkehrfunktion und die Umkehrfunktion ist wieder eine Permutation.

5:58 Formal können Sie die so definieren und dieser Umkehrpermutation ist der Wert an der Stelle I j genau dann, wenn in der ursprünglichen Permutation J auf I abgebildet wurde. Ich kehre die also genau um, wie das eine Umkehrfunktion ja auch tun muss. Ähm, der zweite Begriff ist mehr jetzt aus dem Sortieren motiviert. Das ist die die reverse Permutation, die rückwärts gelesene Permutation. Ich ma einfach genau das. Ich lese die Folge von Zahlen rückwärts. Also so geschrieben, wenn ich ähm diese Permutation als diese Bolge von Zahlen angebe, dann gebe ich einfach die Zahlen umgekehrter Reihenfolge an. Okay, warum man das zweite braucht, werden Sie gleich sehen. Ähm ein Rand eine Randbemerkung an dieser Stelle. Ähm, man kann die diese Menge aller Permutation mit einer Operation verknüpfen, nämlich Funktions äh Komposition. Ich wende zuerst die eine äh Permutation an und auf deren Ergebnis die andere Permutation. kennen Sie aus der Mathematik, denke ich, oder werden es noch kennenlernen. An dieser Stelle ist wieder, wenn Sie wenn Sie das noch nicht kennen, dann können Sie den diese Randbemerkung im Wesentlichen ignorieren. Wir werden darauf nicht aufbauen, aber ich denke, diese Querverbindungen helfen manchmal, damit man sich Dinge besser merken kann.

7:21 Äh, es stellt sich raus, dass diese Menge der Permutation mit dieser Operation der Funktionskomposition eine Gruppe bildet, ähm in der man dann eben auch rechnen kann und äh die hat einen besonderen Namen, weil die auch gut untersucht ist. Da weiß man viel drüber. Für die Informatiker ist sozusagen der Hinweis, wenn man irgendwas mit Permutation macht, dann lohnt sich es manchmal in so ein paar Mattebücher zu gucken, weil da gibt's oft clevere Ergebnisse, die man einfach dann verwenden kann, wenn man sie in die richtige Sprache übersetzt hat. Das ist so der Metakommentar hinter hinter dieser Folie. Äh für das, was wir heute machen, brauchen wir ganz wenig äh dieser Theorie. Äh, alles was wir eigentlich brauchen sind diese grafischen Darstellungen für Permutation. Ähm, hier ist diese diese erste Permutation gemalt. Und wie kommen Sie jetzt von der Permutation zu den Punkten? Ja, es ist einfach auf der X-Achse der der Index und auf der y-Achse der Wert an der Stelle. Das heißt diese 7 2 1 6 3 4 5 lesen 7 2 1 6 3 4 5 indem sie die y Werte vorlesen, dann kriegen Sie die Permutation zurück.

8:38 Warum ist diese Darstellung hilfreich? Einerseits macht sie äh die Verbindung zu inverser und reverser Permutation grafisch. Von hier zu hier muss ich an dieser Achse spiegeln. Dann sehen Sie vielleicht optisch, wenn ich das hier so ein zeichnen bisschen sauberer vielleicht die Punkte hier bekommen Sie, indem sie die Punkte hier an der Achse spiegeln, an der Winkelhalbierenden spiegeln. Und für die reverse Permutation ähm muss ich am Mittel an der Mittel vertikalen spiegeln. Dann bekomme ich hier die Permutation. Also diese diese Definition, wenn die Ihnen wenig intuitiv vorkommen, dann merken sie sich die Bilder und leiten sich die Definition ab, wenn sie sie brauchen. Äh, das finde ich deutlich leichter zu merken und viele der Eigenschaften kann man aus den Bildern dann direkt ablesen. Was besonders hübsch ist und was wir jetzt hier brauchen, ist ähm, dass man Inversionen in dem Bild direkt identifizieren kann. Das sind nämlich alle Paare von Punkten, wo diese Verbindungslinie zwischen den beiden eine negative Steigung hat, die fällt nach unten, wenn ich von links nach rechts laufe.

9:55 Blup, dann sind diese zwei, dann sprechen diese Punkte oder streng genommen ihre X-Koordinaten entsprechend einer Inversion. Und das ist genau dann, wenn ja, wenn ich zwei andere Punkte nehme, z.B. für diese beiden hier, dann ist das keine Inversion, denn da ist ja genau äh sowohl der Index als auch der Funktionswert äh in die gleiche Richtung geordnet.

10:20 Sprich, wenn ich Ihnen so ein Bild gebe, dann können Sie die Anzahl Inversionen zählen, indem Sie einfach die Anzahl Paare angeben, bei denen die gerade die Verbindungslinie eine negative Steigung hat. Okay, was hilft uns das jetzt? Zurück zum Sortieren.

10:39 Erster wichtiger Kommentar. Alles was wir hier tun, die Sortieralgorithmen in diesem Kapitel sind vergleichsorientiert oder vergleichsbasiert. Das heißt, alles was wir über die Daten wissen, ist gegeben, zwei Objekte, welches von denen ist größer oder kleiner? Das war unsere Annahme. Wenn wir in dieser Welt leben, dann können wir für die Analyse uns drauf zurückziehen, dass wir tatsächlich Permutationen sortieren oder die Zahlen von 1 bis n sortieren, denn die sehen ja alle was auch immer die Objekte wirklich sind, ob das Züge nach Abfallszeiten sind oder Unis nach Gründungsdatum oder was auch immer. Für den Algorithmus spielt ja immer nur die Antwort auf seine Fragen eine Rolle und die Frage ist immer, ist X kleiner als Y, ja oder nein? Und dann könnte ich auch alle Elemente durch ihren Rang in der sortierten Folge ersetzen. Dann habe ich Zahlen von 1 bis n und der Algorithmus würde genau das gleiche tun. Deswegen ist für die Analyse dieses ohne Beschränkung der Allgemeinheit meint für die Analyse im Wesentlichen, denn ihre Implementierung soll natürlich schon mit allen Objekten zurecht kommen.

11:48 Das soll ja ein allgemeines Sortierverfahren sein. Um zu analysieren, wie gut es ist, können wir uns aber auf dieses einfache Modell zurückziehen. Und insbesondere für Bubble Sort und Insertion Sort, wo wir ähm die Performance noch nicht so ganz einschätzen konnten. Sie einen sich Selection Sort war komplett Datenunabhängig, immer n quadrat halbe.

12:12 Für Bubblesorten Insertion Sort gibt's aber diese diese spannende Beobachtung hier, dass jeder Swap, den wir in diesen beiden Algorithmen vornehmen, können Sie beim Code noch mal nachschauen, benachbar Indiz ist vertauscht.

12:27 Und das bedeutet, ähm, wenn wir das machen, haben wir immer auch direkt vorher den Vergleich dazu gehabt, dass wir in der Eingabe genau eine Inversion loswerden, nämlich die mit diesen Indizes JJ + 1. Das war eine Inversion, weil wir gerade vorher den Vergleich gemacht haben. Das ist in diesen beiden Algorithmen so. und dann tauschen wir die beiden. Dadurch wird aus dieser Inversion dieser beiden Indizs eine nicht Inversion, denn wir haben ja jetzt eine neue Permutation generiert. Wir haben die Werte verändert. Alle anderen Paare von Indiz sind aber in ihrer relativen Reihenfolge davon unverändert. Das können Sie in dem Bild sehen, wenn Sie sich vorstellen, wir haben so eine Permutation. Hier sind zwei benachbarte Elemente, die waren jetzt eine Inversion. Die beiden würde ich jetzt vertauschen. We hinterher sieht das dann so aus, aber die sind benachbart. Es gibt nichts dazwischen. Ja, also dieser ähm dieser Bereich dazwischen, der ist leer.

13:33 Das sind benachbarte Indizes. Alle anderen Werte, die es in dieser Permutation geben kann, die sind vielleicht hier, vielleicht hier, hier, hier, wo auch immer. Jedenfalls außerhalb von diesem grauen Bereich. Wenn ich also vorher eine Inversion hatte von diesem zu diesem, dann habe ich die jetzt vielleicht nicht mehr, aber ich habe dafür die Inversion zu diesem und das ist für alle Paare so, ich kann sozusagen dadurch, dass die benachbart sind, gar nicht unterscheiden, dass ich diesen Vertausch diese Vertauschung gemacht habe, wenn ich nur von weiter weg gucke, also jede Vertauschung in diesen beiden Algorithmen wird genau eine Inversion los und äh nicht mehr. Das bedeutet, die haben so viele Vertauschungen, wie die Inversionen, wie die Eingabe Inversionen hat. Folgt aus dieser Beobachtung natürlich direkt. Das heißt, alles was wir tun müssen, ist die Anzahl Inversionen analysieren.

14:34 Insbesondere die Laufzeit ist dann mindestens so viel, weil wir die Vertauschung ja mindestens machen müssen. Ähm, die Anzahl Inversion ist hier noch mal als, ich habe ihnen letzte mal gesagt, alles ist irgendwie als Mengenlehrer auszudrücken. Hier ist die entsprechende Formulierung. Also es ist die Anzahl der Elemente in dieser Menge und die Menge enthält alle Paare Ij, sodass i und j zwischen 0 und n -1 geordnet sind und dass die Funktionswerte andersrum geordnet sind. Genau die Definition von Inversion, mehr ist das nicht.

15:09 Das sagt Ihnen auch sofort, warum der Worst Case die rückwärts sortierte Permutation ist, denn da ist egal welches Paar von Punkten ich nehme, die haben alle eine Steigung -1. Also jedes Paar von Indices ist eine Inversion in dieser Permutation und dementsprechend ist deren Anzahl n quadrat halbe etwa. Passt genau zum Worst Case, den wir auch gefunden hatten. Ist jetzt im Nachhinein nicht überraschend und wir können einen Schritt weitergehen und uns fragen, was ist die die mittlere Anzahl Inversionen, wenn ich eine zufällige Permutation bilde?

15:47 Ja, das ist das, was dann in der Animation dieser linkeste Eintrag für für die zufälligen Eingaben war. Ähm, wie sieht's da aus? Äh, da müssen wir theoretisch eine Annahme treffen. Was was heißt jetzt Average Case? In dem Fall die nahliegende Annahme ist, dass alle möglichen Permutationen gleich wahrscheinlich sind. Die Anzahl Permutation von N-Elementen ist N Fakultät. Kennen Sie vielleicht aus Kombinatorik. kommt einfach daher, dass ich ähm n Möglichkeiten habe, mein letztes Element zu platzieren.

16:29 Also, ich baue meine Permutation der Länge n, der hat Indiz von 1 bis n. Jetzt frage ich mich, an welche Stelle packe ich das den größten Funktionswert? Da habe ich n Möglichkeiten. Vielleicht kommt er das dann hierhin. Und wenn ich dann dieses N ignoriere, also das eins kürzere Array anschaue, wo jetzt hier die hier rüber kopiert sind, dann ist das eine Permutation von n - 1. Das heißt, für die habe ich entsprechend n -1 Anzahl Permentation mit n -1 Elementen viele Möglichkeiten und die nehme ich mit n mal, weil ich n Optionen hatte hier meinen Wert n zu platzieren. Es gibt eine Rekursion für die Anzahl der Dinge und die ergibt genau das Produkt n mal n - 1* n -2 bis runter zu 1. Also das ist ja nichts anderes als das Produkt von 1 bis n über i. sollten Sie kennen die die Schreibweise. Was ist die Anzahl Inversionen von so einer Permutation, wenn ich die zufällig aus allen wähle?

17:35 Da kann man erstmal ähm erstmal sich fragen, wie kann man das überhaupt ausrechnen? Das klingt, das klingt erstmal ziemlich kompliziert, ja? Ähm wenn ich eine gegebene Permutation habe in dem Bild, dann kann ich das zählen. Aber was passiert da im Allgemeinen? Es gibt aber einen wunderschönen Trick an der Stelle, den ich Ihnen in dem kleinen Fall für n = 3 zeigen möchte. Da gibt's sechs mögliche Permutationen. Das sind sind diese sechs. Können sich überlegen, das ist alles was passieren kann. Und n3 Fakultät ist auf 6. Das passt also. Und jetzt gruppieren wir die in Paaren, sodass immer eine Permutation mit ihr mit der reversen Permutation als Paar betrachtet wird.

18:18 Und das ist eben deshalb hilfreich, weil in jedem solchen Paar, wenn ich mir irgendwelche zwei Punkte auswähle, dann sind die per Definition einmal so rum und einmal so rum angeordnet. Das heißt, ich habe zwischen den beiden in dieser unteren Permutation eine Inversion, aber oben nicht.

18:43 Wenn ich ein anderes Paar wähle, sagen wir hier in dem äh das muss dann hier spiegeln, die gleichen Elemente, dann habe ich eine Version hier, eine Inversion hier, aber zwischen den passenden Werten hier nicht. Also, ich muss die gleichen Werte nehmen, ja, die gleiche y gleiche Y-Achse.

19:03 Und das ist allgemein der Fall, wenn ich die Permutation rückwärts lese, dann wird halt aus dem, was vorher so rum war, das andersrum. Also die Anzahl Inversionen von einer Permutation und der reversen Permutation zusammen ist immer n über zwei alle Paare. Jedes Paar ist genau in einer der beiden Inversionen. Das heißt, im Schnitt haben beide die Hälfte davon. Das ist natürlich äh nur rechnerisch richtig, aber für den für den Durchschnittswert, für den Erwartungswert ist das Ergebnis. Und wenn das für jedes Paar gilt, dann gilt es auch für eine zufällig gewählte Permutation. Damit haben wir genau die Hälfte vom Worst Case als Average Case für die Anzahl Inversion und das ist Mist, weil immer noch quadratisch.

19:55 Das ist so die Takeaway Message an der Stelle. Und deshalb würde ich auch hier die Frage ähm so beantworten. Ähm vielleicht noch mal hier einmal kurz die Statistik. Ähm, Selection Sword hat eben nie eine Chance von diesen nquadratbe Vergleichen wegzukommen. Macht dafür ganz wenig Swaps. Vielleicht ist das manchmal gut. Äh Bubble Sort und Insertion Sord haben für Eingaben mit wenig Inversionen tatsächlich eine Chance deutlich besser abzuschneiden. Und lassen Sie mich das noch mal einmal zeigen in den Animationen, wo man das dann auch äh direkt sieht. Ich mache jetzt einfach das mal sehr schnell und sehr groß und sie schauen auf die fast sortierte Eingabe. Fast sortiert ist hier tatsächlich genau das. Es gibt wenig Inversion. Wir laufen einmal drüber noch mal. Oh, und schon fertig. Okay. Und für Insertion Sorts können auch ein bisschen größer machen. Äh, sie schauen auf die fast sortierte Eingabe hier.

21:06 Oh, schon fertig. Weil also es es sieht hier aus, als würde der nur einmal drüber laufen. Wenn Sie genauer gucken, dann laufe ich natürlich hier teilweise ein Schrittchen wieder zurück, aber immer nur so ein ganz kleines bisschen. Deswegen geht das hier sehr, sehr schnell. Es sieht fast aus, als wäre es nur ein Durchlauf.

21:31 Also diese beiden Algorithmen haben zumindest auf manchen Eingaben gute Karten, deswegen würde ich denen den den Zuschlag geben, aber im Average Case sind sie eigentlich alle Mist, immer noch quadratisch. Also, was haben wir gesehen? Es sind einfache Algorithmen, die zu kompaktem Code führen. Sie sind auch sparsam, was irgendwie sonstige Bedürfnisse angeht. Sie brauchen keinen Zusatzspeicher, z.B., Aber sie sind im worst case quadratisch und ehrlich gesagt der Average Case ist um diesen Faktor 2 auch nicht wirklich besser. Ähm für manche Nischenanwendung mögen sie aber trotzdem hilfreich sein und da werden wir auch noch mal drauf zurückkommen. Äh insbesondere für sehr kleine Eingaben haben die Verfahren wegen ihrer Einfachheit und ihrem kompakten Code äh manchmal eine Daseinsberechtigung, weil dort die Verfahren, die wir jetzt noch äh im restlichen Verlauf besprechen werden, einfach ein bisschen mehr Overhead generieren. Aber als reine Einsatz äh als reine Satierfunktion skalieren sie einfach nicht mit größeren Eingaben.