Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Mergesort: Informatik (deutsch)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 42 Zeilen
- Hi, schön, dass ihr wieder da seid. Heute geht's mit dem nächsten Sortieralgorithmus weiter. Merge Sort, wie immer ganz ohne Code, sondern nur
- der Allgemeinablauf des Sortieralgorithmus. Wie bei den Videos vorher habe ich wieder die gleiche Zahlenreihenfolge
- dabei und Merch Sort ist ein Sortieralgorithmus und gehört zu den Divide and Conquer Verfahren, also Teile und Herrsche. Das
- heißt, das Problem wird so lang zerlegt, bis es sich selbst löst oder bis es trivial lösbar ist und danach werden die kleinen gelösten Problemchen wieder
- zusammengebaut und so hält man dann die endgültige Lösung. Und bei Merch Sort funktioniert das Ganze so, dass
- wir ja ein großes Problem haben, nämlich eine in dem Fall hier eine Zahlenkette, die wir sortieren wollen. Und die teilen wir jetzt in immer kleinere Probleme
- auf. Das heißt, wir halbieren erstmal einfach immer diese Kette. In dem Fall haben wir eine ungerade Zahl. Da würde ich einfach mal sagen, wir
- teilen durch zwei und schmeißen das Komma weg. Also typisches Integer durch zwei teilen oder sowas. Das bedeutet, wir haben hier vorne dann eine fünfer
- Gruppe und hier hinten, nee, stimmt nicht. Wir haben vorne die vierer Gruppe und hinten die fünfer Gruppe. Meine Farbe ist nicht da. Wir teilen hier.
- Das heißt, wir bekommen zwei Gruppen. Einmal hier die 5 9 1 4 und hier drüben den Rest. 6 7 3 2 8
- Und jetzt machen wir das Ganze rekursiv bei diesen Gruppen weiter, bis nur noch ein Element übrig bleibt. Das heißt, wir teilen wieder hier durch, bekommen hier
- die 59, hier die 1 4. Ähm, hier haben wir wieder ungerade. Das heißt, vorne ist die kleinere Gruppe 67, hinten die große
- 3 2 8 und das geht weiter. Hier gibt's noch mal zwei Gruppen. Die fünf und die neun, die 1 und die 4.
- 6 7. Und hier sind es noch ein paar mehr Schritte. Die kleine Gruppe ist vorne, das heißt
- die drei steht einzeln. Die 28 hier, die 28 teilt sich jetzt noch mal auf in 2 und 8. So, jetzt stehen alle Zahlen einzeln und eine Zahl
- für sich ist schon sortiert. Das haben wir auch äh bei Quicksot z.B. schon mal gesehen und das ist sozusagen die
- Trivialannahme, also das Problem an sich ist lösbar. Also die fünf an sich ist sortiert. Und jetzt können wir ähm diese Probleme wieder zusammenfügen. Das
- heißt, die Pärchen, die sich zuletzt geteilt haben, die werden jetzt angeschaut und verglichen, welches größer ist und entsprechend sortiert.
- Also hier wird die zwei und die acht betrachtet. Das war das letzte Pärchen, das sich geteilt hat. äh oder ist die ist die tiefste Ebene,
- auf der sich was geteilt hat und die stehen schon in der richtigen Reihenfolge. Das heißt, die werden jetzt wieder zusammengefügt.
- Diese ganze Zusammenfügearbeit mache ich jetzt einfach mal blau. Das heißt, wir halten hier 28. So, und jetzt kann ich hier auf der
- nächsten Ebene weitermachen, wo die Teilungen stattgefunden haben. Die 59 sind auch schon stehen auch schon in der richtigen Reihenfolge. Die 14 steht auch
- schon in der richtigen Reihenfolge. Die 67 auch. So, und jetzt haben wir hier die 3 und die 28. Und die müssen jetzt auch noch
- gemerged werden, also zusammengefügt werden. Deswegen heißt der Sortieralgorithmus ja auch Merch Sort. Und dazu wird immer das erste Element
- oder die ersten beiden Elemente dieser Zahlenketten verglichen und das kleinste wird aufgeschrieben. Also deswegen würde jetzt hier die drei
- mit der zwei verglichen. Die zwei ist kleiner, deswegen ist die zwei schon mal weg. Jetzt vergleiche ich noch die drei mit der A. Da ist die drei kleiner.
- Die drei schon mal wegstreichen. Die acht bleibt übrig. Als einzige kann ich noch dazu schreiben. Das ist also das Ergebnis hier.
- So. Dann gehen wir bei der Trennung wieder zurück. Die sind ja getrennt worden. Das heißt, diese beiden Gruppen hier werde ich auch wieder merchen. Ich
- vergleiche wieder am Anfang die vordersten beiden Elemente, also die 1 mit der 5. Die ein ist kleiner, deswegen kann ich mir die ein schon mal
- aufschreiben. Dann vergleiche ich die fünf mit der vier. Da ist die vier kleiner. Kann ich auch schon mal wegstreichen.
- So, jetzt ist eine komplette Gruppe weg. Das heißt, ich kann die andere Gruppe einfach so übernehmen, weil es ist nichts mehr zum Vergleichen da. 59.
- Das gleiche machen wir hier drüben auch noch mal. Die zwei und die sechs werden als erstes verglichen. Ich schreibe die zwei auf.
- 3 und die sech werden verglichen. Die drei ist kleiner. Die sech und die 8 wird verglichen. Die sechs ist kleiner. Die sieben und die acht wird verglichen.
- Da ist die sieben kleiner. Dann bleibt die acht als einzige übrig und die übernehme ich einfach mit. So, jetzt sind schon die letzten beiden Gruppen
- da. Da wird jetzt auch noch mal ganz normal gemerged. Die 1 wird mit der 2 verglichen. Also schreibe ich die 1 auf, die 4 und die 2 wird verglichen. Da
- schreibe ich die zwei auf, weil sie kleiner ist. Dann wird die vier mit der 3 verglichen. Da gewinnt die drei. Und so geht's jetzt weiter und dadurch
- entsteht jetzt unsere Zahlenfolge, so wie sie sortiert sein sollte. 7 8 und die neun. Und dadurch
- und dadurch haben wir unsere sortierte Zahlenfolge erhalten. Also wir haben noch mal zwei Schritte.
- Erster Schritt divide. Zweiter Schritt Conquer
- und das war schon Merch Sort. Wie immer habe ich noch mal eine Zahlenfolge für euch dabei zum Ausprobieren. Sortiert die doch auch mal so wie Merch
- Sort, wie ihr es gerade gesehen habt. Die Lösung gibt's wie immer unter dem Video. Ich hoffe, ich hat euch Spaß gemacht und ich habe euch ein bisschen
- geholfen. Bis zum nächsten Mal. Tschüss.
Zum Nachlesen
MergesortMergesort (von englisch merge ‚verschmelzen' und sort ‚sortieren') ist ein stabiler Sortieralgorithmus, der nach dem Prinzip teile und herrsche (divide and …
Merge InsertionMerge Insertion (auch bekannt als Ford-Johnson-Algorithmus) ist in der Informatik ein rekursives, vergleichsorientiertes Sortierverfahren, das mit weniger …
Merge-AlgorithmenMerge-Algorithmen werden in vielen Algorithmen als Unterprogramm verwendet. Ein bekanntes Beispiel dafür ist Mergesort.
Teile-und-herrsche-VerfahrenDie binäre Suche nach einem Schlüssel ist eine der ersten algorithmischen Anwendungen des Prinzips von „teile und herrsche“. Sie lässt sich zu den …