Video 7-4: Merging

0:04 Im nächsten Abschnitt schauen wir uns den ersten wirklich praktikablen Sortieralgorithmus an. Das ist Merchort. Äh, das ist einer von zweien Merchsort und Quicksort, den wir uns dann nächste Woche auch noch anschauen, die im Wesentlichen die praktischen Einsatzzwecke vom Sortieren dominieren und da auch sehr gut funktionieren. Insofern äh ist das keine keine keine schlechte Dominanz. Ähm, Merch wird eingesetzt in in all diesen Software Frameworks. Quicksord, in denen Sie sehen, da ist fast äh das ein sehr großer Überlapp, weil meistens auch in Java äh beide Algorithmen angeboten werden. Wir werden noch drauf zu sprechen kommen, warum genau und wann genau. Ähm, das hier ist sozusagen nur vorweg. Äh insbesondere Quicksort hat auch eine interessante Geschichte, ähm die sich lohnt ein bisschen äh zu erzählen und sozusagen ein bisschen die Wertschätzung für diese zwei schönen Algorithmen äh vorab an äh erheben und äh auch ein bisschen Werbung für meine eigene Arbeit machen. Äh wir haben uns viel mit Sortieralgorithmen beschäftigt, insbesondere mit Verfahren eben, die dann in Standardbibliotheken zum Einsatz kommen. Beim Sortieren ist meine mein persönlicher Einschätzung immer, man kann da ganz viel machen und man kann sich spannende Elfenbeinturmalgorithmen ausdenken, aber eigentlich ist sortieren so gut verstanden, wenn das irgendwie interessant sein soll für mich jedenfalls, dann muss es in der Praxis auch irgendwie ein Vorteil bringen. Na ja, dazu ähm vielleicht ähm bei gegebenem Punkt am Ende von dem Kapitel noch ein bisschen mehr. äh finden Sie auch jede Menge Zeug. Dann wenn sie wenn Sie fragen, dann überschütte ich sie mit mit Links. Was hat's mit Merchort auf sich?

1:48 Die Lessen von diesem letzten Abschnitt zu den primitiven Verfahren war ein bisschen ähm ist vielleicht ein bisschen kurz gekommen am Ende. Jedes Verfahren, das bei das auf Swaps basiert und immer nur benachbarte Elemente vertauscht, ist verdammt bei diesem quadratischen Average Case festzuhängen, denn ich werde dann immer nur eine Inversion los. Ich habe aber ganz viele Inversionen in den meisten Eingaben, da werde ich nicht von wegkommen. Das heißt, wir müssen was radikal anderes machen. Insbesondere müssen wir weg von dieser Idee, immer nur ein Element irgendwo äh zu platzieren und dann den Rest rekursiv zu machen. Und die die große große andere Idee, die die man da haben kann, ist statt Einzel Elemente zu platzieren, die Eingabe in zwei Teile zu teilen und auf denen beiden rekursiv was zu machen und dann irgendwie zu reparieren oder zusammenzustöpseln, was man dabei so äh kaputt verbessert hat. Das ist die Idee von Divide and Conquer Algorithmen. Äh wenn Sie das systematischer und sozusagen bisschen breiter hören wollen, müssen sie in die effiziente Algorithmen kommen. Äh wir werden es hier für Algorithmen und Datenstrukturen im Wesentlichen bei den Sortieralgorithmen sehen. Die Idee ist, dass man die große Eingabe, die man am Anfang bekommt, irgendwie kleinhaut in mehrere Teile, die man unabhängig voneinander lösen kann.

3:18 Im Fall von Merchort ist die Idee konzeptionell die Eingabe in zwei Teile zu zerteilen. Ich sage konzeptionell, weil wir für diesen Teilschritt gar nichts machen. Wir sehen einfach den ersten Teil als einen Teil an und den zweiten Teil der Eingabe als einen anderen und dann sortieren wir die beide mit Merch Sort rekursiv. Wenn wir daraus zurückkommen, dann sind diese beiden Teile sortiert und dann möchte ich gerne aus diesen zwei sortierten Teilen die sortierte Gesamteingabe machen.

3:51 Das ist die Idee. Lassen Sie mich, bevor wir da weiter im Allgemeinen beharren, das einfach kurz zeigen, wie das funktionieren soll, warum das funktionieren soll. Das nennt sich Merging, daher der Name Merge Sort. Auf Deutsch könnte man sagen verschmelzen, wobei da ähm na ja, ist der Begriff ähm als als Bild habe ich das so angedeutet, dass wir zwei Teile der Eingabe haben, die intern sortiert sind. Deswegen sind es diese Dreiecke, aber ich weiß nicht, wie sich die Elemente links und rechts jeweils zueinander verhalten und mein Ziel ist daraus, eine gesamtsortierte Eingabe zu generieren. Die Eingabe, diese zwei sortierten Teile, also ein ein Teil von der Eingabe, der sortiert ist, das nennt man in diesem Kontext einen Run. ähm hat sich so eingebürgert. Ich fürchte, runig, heißt manchmal was anderes. In dem Kontext vom Sortieren ist es ein zusammenhängendes ein Teile Array, das das sortiert ist, also irgendwie so ein Bereich zwischen zwei Indiz.

4:59 So aussehen. Wir haben hier unsere Balken wieder. Das ist die die Eingabe. Wie kann ich jetzt aus diesen zwei sortierten Teilen ein sortiertes Gesamtergebnis machen?

5:10 Die Idee ist, wir bauen das Gesamtergebnis von links nach rechts auf, vom kleinsten zum größten. Wo kann in unserer Eingabe das Minimum der gesamten Ausgabe, das hierhin soll, wo kann das stehen? Na ja, die sind sortiert, also eigentlich nur am linken Rand von diesen beiden Runs. Das sind zwei Möglichkeiten. Wir machen einen Vergleich und finden raus, welche es ist. Also, ich vergleiche die beiden. Der hier gewinnt, damit bewege ich den in die Ausgabe und habe das erste Element der Ausgabe produziert. Und eigentlich machen wir jetzt einfach nur das gleiche immer wieder, denn ich bin jetzt in der gleichen Situation wie vorher. Wenn ich mich frage, wer gehört hier die nächste Position der Ausgabe? Das ist das Minimum unter allen verbliebenen Elementen jetzt, wo der hier weg ist. Und das ist wieder entweder der hier oder der hier. Also frage ich wieder, wer ist denn von euch größer? Geht wieder diese erste äh Run. Dann bewege ich das Element rüber und dann geht das Ganze so lang so weiter, bis ähm ich die ganze Eingabe verarbeitet habe. Hier gewinnt mal der andere Run, dann wird der rüber bewegt.

6:21 Dann vergleiche ich hier wieder, beweg den rüber noch mal. Dann kann es einem irgendwann passieren, dass eine dieser Eingaberuns schon erschöpft ist, während in dem anderen noch Elemente da sind. Das ist noch einfacher. Dann weiß ich, diese ganzen Elemente müssen jetzt einfach darüber bewegt werden und dann machen wir das halt auch äh eins nach. Das ist merching. Okay, also tatsächlich äh relativ relativ einfach oder einfacher Algorithmus.

6:52 Ähm, bevor wir dann weitermachen, ähm wir dann bald aufhören für heute, einmal noch eine letzte Frage. Wie lange dauert das denn? Paar mehr Leute waren wir vorhin, vielleicht sind ein paar schon verschwunden.

8:02 Äh, jemand noch aktiv am Krübeln? kann ich Ihnen ja mal ihre die Ergebnisse zeigen. Ähm durchaus verschiedene Meinung dazu. Also, ich nehm es hier mal einfach äh vorweg.

8:25 Die richtige Antwort ist Linearzeit. Ja, sie können jetzt noch Ihre Antwort verschieben. Sie können es auch lassen. Ähm ist ja nur informativ gemeint. Warum ist es Linearzeit? Ähm ist am schönsten zu sehen, wenn Sie sich noch mal vor Augen führen, was wir hier in jedem Schritt machen. Wenn ich hier n Elemente habe und hier noch mal n, dann habe ich hier im Ergebnis 2n. Geht ja nichts verloren. Und für jedes Element, dass ich hier in der Ausgabe produziere, mache ich einen Vergleich eventuell und dann eine Vertauschung darüber.

9:01 Manche Elemente gegen Ende haben sogar äh das Glück, dass sie gar nicht verglichen werden und nur bewegt werden, dann ist es noch ein bisschen günstiger. Aber jedes Element hier drüben wird nach sozusagen konstant viel Arbeit ein wird ein neues Element hier an die Ausgabe hinzugefügt. Das heißt, nach 2n mal konstant viel Arbeit habe ich immer noch linear viel Arbeit verrichtet. O von n Arbeit.

9:34 Äh, letzter Punkt hierzu ist, was wir bisher gesehen haben, beschreibt Merchging als Eingabe, zwei sortierte Teilarrays und Ausgabe ein gesamtsortiertes Array. Und so wie ich das hier in dem Beispiel geschrieben habe, wir lesen von hier und schreiben nach da, funktioniert es auch gut. äh funktioniert auch gut, wenn man tatsächlich irgendwelche physischen Objekte sortiert, die man bewegen kann. In einem Array von Objekten ist das aber so ein bisschen unbequem und da steckt auch ein fundamentales Problem in Merchsort dahinter. Was wir hier eigentlich gerne tun möchten, ist zwei benachbarte Bereiche in dem Array. Also, ich habe hier mein Array A, dann habe ich einen Run hier und den anderen direkt danach. Die gehen hier von low bis high und mid ist hier dieser das Ende vom ersten Run. Die die sind direkt nebeneinander in dem Array. Das heißt, ich kann theoretisch die einfach ersetzen durch den durch das Ergebnis von dem Merch. Das ist also mein Ziel.

10:35 Es stellt sich aber raus, dass es, wenn Sie das, wenn Sie mal versuchen, das zu tun, direkt in dem Array, der Ihnen als Eingabe gegeben ist, ist das extrem knifflig. Da steht nicht unmöglich, weil es nicht unmöglich ist, aber es ist viel viel aufwendiger. Man braucht äh aufwendige clevere Algorithmen, um das zu tun, die auch langsam sind. Die sind praktisch aus praktischer Sicht irrelevant. Ähm es ist sehr knifflig, das ohne irgendwie einen Pufferbereich zu machen, wo ich Elemente mal auslagern kann, um einfach zu manövrieren. Deswegen werden wir tatsächlich in unserer Methode das auch so tun. Wir verschieben die Elemente erstmal in einen Arbeitsbereich und mergen sie dann zurück in das Array. Das passt dann auch zu der Animation, die ich Ihnen gezeigt habe. Da war das quasi schon ohne viel zu drüber zu reden, die Eingabe der Runs auf der linken Seite und die Ausgabe auf der rechten Seite produziert.