Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
MergeSort
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 107 Zeilen
- Geteiltes Leid ist halbes Leid, sagt das Sprichwort. Und das kann man auch von Arbeit sagen. Geteilte Arbeit ist halbe Arbeit. Teile die Arbeit auf und man hat weniger davon.
- Jeder macht dann die Hälfte. Und das ist das Prinzip nach dem MerchSort funktioniert. Wenn wir eine Reihe von n Elementen haben und die wollen wir sortieren,
- dann können wir als erstes sagen, gut teile es auf in zwei Hälften. Die eine Hälfte bekommt der eine, die andere Hälfte der andere und jeder sortiert mal seine Hälfte.
- Und wenn dann jeder seine Hälfte sortiert hat, müssen wir nur am Schluss aus zwei sortierten Teillisten wieder eine sortierte machen. Das ist also die grobe Idee von MerchSort. Teile die Liste
- in zwei möglichst gleich große Teile auf und sortiere diese getrennt und anschließend sortiere die beiden Teillisten, die dann ja sortiert sind, zu einer sortierten Liste zusammen.
- Und werden wir gleich sehen, es ist einfacher, wenn man bereits vorsortierte Teillisten hat, diese zu einer sortierten Liste zusammen zu sortieren, als wenn noch nicht sortiert wurde.
- Wir machen mal kurz ein Beispiel, wie das Ganze funktioniert. Die Zahlen wollen wir jetzt aufsteigen, sortieren und dann ist der erste Schritt. Wir teilen
- sie in zwei möglichst gleich große Teile ein. Nun geht das nicht auf. Das sind ja eins, zwei, drei, vier, fünf, sechs, sieben, acht, neun,
- verschiedene Zahlen. Neun kann man nicht ohne Rest durch zwei teilen. Deswegen möglichst gleich groß. Wir werden das hier so machen, dass die rechte Seite dann in diesem Fall um eins größer ist.
- Das heißt, die Stelle, wo wir teilen, ist hier. Dann haben wir eine Teilliste hier. Das sind diese vier Zahlen und die werden nun sortiert. Wir sortieren also beide Listen getrennt.
- Die eine Liste ist dann sortiert eins, drei, sechs, sieben. Und die andere sortieren wir ebenfalls. Wir sortieren die getrennt. Also einmal hier sort und das sort.
- Bei der anderen kommt heraus dann also eins, zwei und die zwei ist hier doppelt. Also stehen dann da zwei zweien und dann eine sechs und eine acht. Nun müssen diese beiden Listen wieder zusammensortiert
- werden. Das heißt, das wird jetzt zusammensortiert und das ist der Verschmelzungsschritt. Eins, eins, zwei, zwei, drei, sechs, sechs, sieben, acht. Am Schluss haben
- wir dann hier alles sortiert und es kommt auch jede Zahl so oft vor, wie sie in der oberen unsortierten Liste vorgekommen ist. Das ist die Idee. Jetzt haben wir die verstanden.
- Jetzt können wir sie als Pseudocode aufschreiben und wir werden dabei das noch ein bisschen lax angehen und nicht alles bis zu Ende ausdiskutieren. Wir werden noch ein paar
- Baustellen offen bleiben und die schauen wir uns dann anschließend an. Also der Algorithmus heißt, das haben wir schon gesagt, Merge Sort und er bekommt eine Liste von Zahlen und
- wir werden jetzt hier nicht von eins bis n durchgehen lassen, sondern einfach von einer linken bis zu einer rechten Grenze und warum wir das tun, wird später herauskommen.
- Also l kann zum Beispiel eins sein, r kann n sein und dann ist es genauso wie vorher, aber es kann beliebige zwei Grenzen sein, die dann eben einen Teilbereich dieser Liste betreffen.
- So, jetzt müssen wir am Anfang natürlich uns anschauen, ist denn da mehr als ein Element drin. Also wenn l kleiner als r ist, nur dann müssen wir was tun. Wenn l gleich r ist, dann ist da
- nur ein einziges Element in der Liste und dann ist das schon sortiert. Da müssen wir nichts machen. Also erst wenn mindestens zwei Elemente, also größer gleich zwei Elemente in der Liste,
- erst dann muss ich was tun und jetzt will ich die teilen, diese Liste. Ich will sie in zwei möglichst gleich große Teile aufteilen und die Stelle, an der ich teile,
- die nenne ich m. Also m soll die Mitte, die ungefähre Mitte zwischen diesen Bereichen l und r sein, also zwischen den linken und der rechten Grenze des Teilbereiches in der Liste,
- die ich sortieren möchte. So und dann sortiere ich beide Teile erstmal getrennt. Also sortiere a von l bis m-1 und das ist sozusagen der linke Teil. Ja und
- dann sortiere ich auch noch den rechten Teil. Der fängt von m an und hört r an der rechten Stelle. Dieses r, das ist das r hier oben, die rechte Stelle hört r auf.
- Und damit habe ich durch diese zwei Teile hier die Liste komplett aufgeteilt. Der eine geht eben von l bis m-1 und der andere Teil von m bis r. Zumindest die Liste in diesem Bereich
- von l bis r habe ich damit aufgeteilt. Jetzt sind die Teillisten sortiert und jetzt muss ich nur noch merchen und da rufe ich eben ein Merge-Algorithmus auf und der kriegt dann diese
- beiden Teile hier a von l bis m-1 und a von m bis r übergeben und sortiert die zusammen. Da haben wir noch ein paar Sachen zu tun. Was müssen wir noch machen? Na ja,
- erstens müssen wir hier herausfinden, wie wir die Mitte berechnen. Zweitens ist hier dieser Merge-Algorithmus, den müssen wir uns genau anschauen und dann,
- und das wird tatsächlich das Spannendste an der Geschichte sein, wird das hier sein. Wie machen wir denn diese Sortierungen überhaupt? Haben wir das Problem jetzt nicht nur verlagert
- auf ein etwas kleineres Problem? Ja, dafür müssen wir eine Lösung finden. So, also das erste Problem, wir haben hier diese Liste und wir haben irgendwo unsere linke Grenze,
- das ist l, und wir haben irgendwo unsere rechte Grenze und das ist r. Und nun schauen wir mal, wie viele Elemente haben wir hier? 1, 2, 3, 4, 5, 6, 7, 8, 9. Das geht
- nicht auf, das ist der eine Fall und der andere l, hier geht es auf. Da sind es jetzt acht Stück. So, wenn wir es also acht Stück haben, dann wollen wir genau an dieser Stelle das m haben,
- weil nachher soll ja die Liste, die eine Liste von l bis m-1 gehen und der andere Listenteil von m bis r. Wenn wir aber den oberen Fall haben, dass es ungerade vier sind,
- dann machen wir das m hier hin und hier ist dann m-1. Dann wird die linke Liste ein bisschen kleiner als die rechte Liste. So, wie rechnen wir das jetzt aus?
- Da gibt es eine einfache Formel für und die geht so, m ist gleich und dann nimmt man links plus rechts geteilt durch 2. Man nimmt den Mittelwert, also l plus r geteilt durch 2. Wenn Ihnen das
- jetzt nicht klar ist, machen Sie mal ein paar Beispiele, dann werden Sie feststellen, ja das ist es genau. Der Mittelwert ist quasi die Mitte zwischen den beiden Zahlen in dem Zahlenstrahl.
- In diesem Fall, wo eine ungerade Zahl von Elementen drin ist, kriegt man hier, wenn man l plus r richtet, etwas Gerades raus und bekommt genau dieses mittlere Element,
- was zwischen hier 4 sind links, dann kommt das m und dann sind 4 rechts in der Liste. Kriegt man genau das raus und dann schneiden wir die eben an
- der Stelle m-1 und m. Und in dem Fall, wo man eine gerade Anzahl von Elementen hat, ist r plus l ungerade und dann muss man runden und wir runden hier auf. Also aufgerundet,
- denn nur so kriegen wir das etwas größere m hier, damit wir dann links von dem m schneiden können. Also das ist die Formel, die wir in unseren Algorithmus einsetzen müssen,
- um das m zu berechnen. Gut, das haben wir hier also an die Stelle, wo wir das m berechnen schon mal eingefügt. Jetzt zweites Problem haben wir hier unten diesen Merge-Algorithmus, über den
- wollen wir jetzt reden. Schauen wir uns nochmal das Beispiel an, was wir eben schon gesehen haben. So, das ist jetzt unser a und hier ist l und hier ist r und das war die Stelle, wo wir die Grenze
- gezogen haben. Das heißt, hier ist m und hier ist m-1. So, diese beiden Teillisten sind jetzt schon sortiert und unsere Aufgabe ist, die zusammen zu sortieren. Und damit das gelingt, müssen
- wir diese Zahlen, die dort drin sind, in der richtigen Reihenfolge hineinschreiben, in das Re. Und dabei ist die Gefahr groß, dass wir Zahlen, die wir noch nicht einsortiert haben,
- überschreiben. Und damit das nicht passiert, gönnen wir uns einfach ein zweites Re und das nennen wir b. Und das soll genauso groß sein wie a,
- bzw. wenn wir nur auf einem Teil arbeiten, dann soll das ganz genau im selben Bereich sein. Das heißt, hier soll auch l sein und da soll r sein. Und wir werden jetzt nacheinander diese
- Zahlen in der richtigen Reihenfolge hier unten sortiert hineinschreiben. Und wenn wir das haben, müssen wir nur noch alle sortierten Zahlen hier wieder in einem Schwang
- zurückschreiben und dann haben wir sie in a wieder in der richtigen Reihenfolge stehen. Wie sortiert man nun zwei solche sortierten Listen zusammen?
- Das ist ganz einfach. Wir brauchen zwei Finger. Wir müssen hier immer an den Anfang der beiden Listen, müssen wir die Elemente vergleichen. Und weil
- es hier beides mal eins ist, können wir dann jedes beliebige nacheinander nehmen. Wir nehmen zum Beispiel das aus der linken Liste zuerst und dann schreiben wir das unten
- rein. Dann ist als nächstes die 3 dran. Und weil die 3 größer ist als die 1 hier, nehmen wir natürlich zuerst dieses hier, schreiben das rein,
- setzen es hoch. Und dann nehmen wir das und schreiben es rein und so weiter. Das heißt, wir brauchen zwei Finger, die jeweils auf das nächste Element in den beiden Listen
- zeigen. Und die nennen wir mal IL, das ist das i für die linke Liste. Und das andere nennen wir IR, das ist der Finger für die rechte Liste. Und die beiden Elemente, auf die diese Finger
- zeigen, die vergleichen wir miteinander und tragen dann immer das kleinere ein. Und zwar hier an die nächste freie Position innerhalb der Liste b. Gut,
- schreiben wir den Algorithmus mal auf. Also Algorithm Merge haben wir ihn genannt und er bekommt diese zwei Teil-Arrays übergeben.
- Und das eine geht zu einem m-1 und das andere fängt dann bei m und geht bis r. Und dann haben wir eben diese beiden Grenzen hier oben genannt. Wir brauchen eine Variable IL,
- eine Variable IR und eine Variable j. Und IL ist also der aktuelle Zeiger auf die linke Liste. Den stellen wir auf die erste Position, das ist l.
- Und IR, das ist dieser andere Zeiger hier, der steht am Anfang auf dem Beginn der zweiten Liste und das ist m. Und dann haben wir j und das sehen wir da gerade noch. j steht
- auch auf l. Und am einfachsten ist es das j in eine Vorschleife hineinzupacken und zu sagen, ja das j läuft jetzt einmal von l bis r durch.
- Und an jeder Stelle bei jedem Schleifendurchlauf tragen wir ein neues Element dort in das REB ein. So was tun wir? Nun wir schauen uns die beiden Elemente an,
- auf die diese beiden Finger zeigen. Das ist in dem Fall beides einzeln. Und die vergleichen wir, später wenn es nicht einzeln sein, sondern wir werden die
- immer weiterziehen. Dann vergleichen wir die beiden Elemente und wenn das linke kleiner gleich als dem rechten ist, dann nehmen wir das linke zuerst und ansonsten nehmen wir das
- rechte. Also wenn a von IL, das ist jetzt das Element, wo der linke Finger drauf zeigt. Wenn das kleiner oder gleich a von IR ist, das ist das Element, wo der zweite Finger drauf zeigt.
- So, wenn das der Fall ist, dann nehme ich das Element aus der linken Liste und trage es in b ein. Dann ist also b von j ist dann a von IL. Ich habe also
- jetzt das aus der linken Liste genommen und jetzt muss ich das IL natürlich um eins weiter schieben. Denn jetzt habe ich das ja schon nach b geschoben.
- Also IL wird zu IL plus eins. In dem anderen Fall, wenn jetzt also der rechte Finger auf das kleinere Element zeigt, dann nehme ich als nächstes Element in die b-Liste das a von IR.
- Und da muss ich dementsprechend auch IR um eins weiter schieben, um dann das nächste Element zu bekommen. Jetzt achten Sie kurz auf dieses ILF hier.
- Das gibt die Idee wieder, die wir nehmen. Wir nehmen das kleinere Element. Da werden wir gleich aber noch was dazuschreiben, noch weitere zusätzliche Bedingungen
- hinzuschreiben. Und die kommen daher, dass diese beiden Finger, IL und IR, dass die, wenn sie laufen, hier irgendwann einmal aus ihren Bereichen rauslaufen können.
- Und das müssen wir abfangen. Sobald das IL hier rausläuft, müssen wir dafür sorgen, dass in Zukunft von links nichts mehr gelesen wird. Dann müssen wir immer
- in den l-Zwahl hineinkommen und immer nur von der rechten Liste noch Elemente nehmen. Und wenn jetzt das IR hier rechts rausläuft, dann ist es umgekehrt.
- Dann müssen wir nur noch aus der linken Liste nehmen. Das heißt, in jedem Fall ist es von links bekommen. So, also der Algorithmus geht los. Wir haben alle diese
- Variablen auf ihre richtige Position gestellt und nun wollen wir hier ein Element einfügen. Und welches ist das? Ja, wir schauen uns an. Ist IL kleiner als IR? Ja, beide zeigen auf eine Eins.
- Das heißt, hier dieses Element nehmen wir, schreiben es hier unten rein und dann können wir diesen Zeiger um eins weiter schieben. Der steht jetzt auf dem nächsten Element. So,
- und jetzt kommt die Schleife in ihre nächste Runde hinein. Das heißt, jetzt wird das j um eins weiter geschoben und dann vergleichen wir wieder die beiden Elemente, auf die die beiden Finger zeigen.
- Und in dem Fall ist das hier das kleinere. Das heißt, wir sind im l-Zwahl, schreiben jetzt hier die Eins rein und verschieben diesen Zeiger,
- diesen Zeiger hier um eins weiter. Jetzt sind wir mit der vorbei. Das j geht um eins weiter. Wir sind jetzt hier, vergleichen die zwei und die drei, stellen fest, aha,
- es ist wieder die rechte Seite, die kleiner ist. Also hier kommt eine Zwei rein und dann verschieben wir diesen hier um eins weiter und dann in der nächsten Runde natürlich das
- j wieder um eins weiter. Jetzt ist hier wieder das kleinere, also wieder eine Zwei. Wir müssen wieder das hier um eins weiter verschieben und jetzt sind wir hier mit dem j.
- Und nun ist es wieder die linke Seite, die kleiner ist. Das heißt, jetzt kommt eine Drei hier hinein und wir verschieben diese linke Seite um
- eins weiter und das j wieder um eins weiter. Jetzt sind sie wieder gleich und bei kleiner gleich nehme ich immer links bevorzugt. Also jetzt wieder hier oben die Sechs.
- Jetzt kommt die Sechs von der anderen Seite und jetzt wird es spannend. Jetzt kommt hier die Sieben hinein, die ist kleiner als die Acht und in diesem Moment
- schieben wir das IL über die grenzerlinken Dateiliste hinaus. Und jetzt ist ein Problem, wenn wir jetzt einfach so weitermachen, wie es hier steht, ist das IL ja, das a von IL ist
- eins und ist kleiner. Jetzt würde ich in der nächsten Runde hier eine Eins reinschreiben, die Eins, die ich ja bereits hier an die Stelle schon eingetragen habe und das ist falsch.
- Das heißt, das muss ich jetzt abfangen. Ich muss hier schreiben, wenn das IL kleiner als m ist, nur dann darf ich hier reingehen. Jetzt ist es gleich m und jetzt muss ich auf jeden
- Fall in den IL-Zfall hineinlaufen. Das gleiche würde auch passieren, wenn jetzt hier diese rechte Seite zuerst drauf laufen würde, dann müsste ich dafür sorgen,
- dass wenn das IR größer als das r wird, dass wir dann nicht mehr links sind und das fangen wir auch noch an, indem ich hier noch IR größer als r als Möglichkeit eingebe.
- Also sobald, muss ich hier klammern, sobald ich einmal mit der linken Seite rausgelaufen bin mit dem linken Finger, bin ich auf jeden Fall in dem Fall hier drin. Wenn
- ich aber nicht links rausgelaufen bin, aber mit dem rechten rausgelaufen bin, dann bin ich in jedem Fall hier drin, in dem linken. Und wenn beides noch innerhalb der Listen ist,
- also sowohl IL noch kleiner als m ist, als auch IR kleiner als m ist, dann vergleiche ich die beiden Elemente und nehme jeweils das kleine hinein. Und das ist jetzt der fertige Algorithmus.
- Ich habe noch eine Sache vergessen, ganz am Schluss muss ich natürlich das a noch wieder zurück kopieren, das b noch wieder zurück kopieren in das a. Das schreibe ich mal kurz so
- hin. Also das ist hier kopiere b nach a zurück. Und dann haben wir hier den Merge Algorithmus. Jetzt haben wir diese ersten beiden Punkte geschafft. Jetzt müssen wir uns nur anschauen,
- wie sortieren wir denn jetzt diese beiden Teillisten. Ja, was haben wir denn für Möglichkeiten? Bisher haben wir ja noch nicht so viele Sortieralgorithmen uns angeschaut.
- Was haben wir? Wir haben Selection Sort. Das könnten wir doch mal ausprobieren. Das hier ist also unser erster Versuch.
- Was hat der für eine Laufzeit? Naja, ich habe hier Selection Sort aufrufe. Wenn ich hier insgesamt n Elemente drin habe, dann würde ich hier jeweils mit etwa
- n halbe Elementen reingehen, vielleicht auch mal n minus eins halbe. Also Laufzeit jeder Aufruf von Selection Sort braucht also O von n geteilt durch zwei zum Quadrat.
- Und was ist das? Das können wir ausmultipizieren. Das ist der n Quadrat Viertel und das Viertel können wir wegnehmen, ist ja eine Konstante. Das heißt, das ist O von n Quadrat.
- Das ist schon ein bisschen frustrierend, denn eigentlich wollten wir ja besser werden durch dieses Aufteilen, sind wir aber nicht, weil die Teile immer noch unter dem Groß O gesehen so viel
- Zeit brauchen, dass es quadratisch läuft. Ja, was bleibt uns jetzt noch übrig? Wir haben noch einen zweiten Sortieralgorithmus. Der ist noch nicht ganz fertig, aber fast.
- Und der heißt Merge Sort. Wie wäre es, wenn wir einfach Merge Sort nehmen, um die Teillisten zu sortieren? Völlig verrückte Idee. Ich schreibe es einmal hin.
- Was heißt das? Das heißt, der Algorithmus ist rekursiv. Er ruft sich selbst auf und zwar nicht nur einmal, sondern sogar zweimal ruft er sich selber auf. Das ist ganz schön verwirrend und
- deswegen werden wir in den nächsten Videos nochmal ausführlich auf Rekursion eingehen und was das bedeutet und auch darauf, wie wir die Laufzeit von diesem Algorithmus bestimmen können.
- Denn die erste Überraschung ist, der Algorithmus funktioniert so, wie er hier steht. Der funktioniert. Das klappt, weil immer wieder zwar er sich selbst aufruft,
- aber auf kleineren Arrays und er bricht ab, sobald diese Eigenschaft hier unten nicht mehr erfüllt ist. Also sobald ich nur noch ein Element habe in der Liste.
- Solange teilt er sich immer weiter auf und dann kommen diese Aufrufe wieder zurück und wenn die beide zurückgekommen sind, kann er Merge ausführen und es funktioniert. Am Schluss kommen alle diese
- rekursiven Aufrufe wieder zurück und dann wird der allerletzte Merge ausgeführt und dann ist das Erri sortiert. Es klappt. Und das große Wunder ist, die Laufzeit von diesem Algorithmus ist nicht mehr n².
- Die Laufzeit ist O von n mal logarithmus n. Also ist besser als O von n². Und wie das sein kann, das sehen Sie dann in einem der nächsten Videos.
Zum Nachlesen
MergesortMergesort (von englisch merge ‚verschmelzen' und sort ‚sortieren') ist ein stabiler Sortieralgorithmus, der nach dem Prinzip teile und herrsche (divide and …
Merge-AlgorithmenMerge-Algorithmen werden in vielen Algorithmen als Unterprogramm verwendet. Ein bekanntes Beispiel dafür ist Mergesort.
Merge InsertionMerge Insertion (auch bekannt als Ford-Johnson-Algorithmus) ist in der Informatik ein rekursives, vergleichsorientiertes Sortierverfahren, das mit weniger …
QuicksortQuicksort (englisch quick ‚schnell' und to sort ‚sortieren') ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile …