Mergesort: Informatik (deutsch)
bleeptrack
https://www.youtube.com/watch?v=yKgzwtqWvFU

Transkript (automatisch erstellt)

0:02 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
0:10 der Allgemeinablauf des Sortieralgorithmus. Wie bei den Videos vorher habe ich wieder die gleiche Zahlenreihenfolge
0:18 dabei und Merch Sort ist ein Sortieralgorithmus und gehört zu den Divide and Conquer Verfahren, also Teile und Herrsche. Das
0:28 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
0:37 zusammengebaut und so hält man dann die endgültige Lösung. Und bei Merch Sort funktioniert das Ganze so, dass
0:47 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
0:55 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
1:04 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
1:12 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.
1:23 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
1:39 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
1:47 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
2:00 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.
2:14 6 7. Und hier sind es noch ein paar mehr Schritte. Die kleine Gruppe ist vorne, das heißt
2:20 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
2:31 für sich ist schon sortiert. Das haben wir auch äh bei Quicksot z.B. schon mal gesehen und das ist sozusagen die
2:39 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
2:47 heißt, die Pärchen, die sich zuletzt geteilt haben, die werden jetzt angeschaut und verglichen, welches größer ist und entsprechend sortiert.
2:56 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,
3:03 auf der sich was geteilt hat und die stehen schon in der richtigen Reihenfolge. Das heißt, die werden jetzt wieder zusammengefügt.
3:12 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
3:22 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
3:31 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
3:40 gemerged werden, also zusammengefügt werden. Deswegen heißt der Sortieralgorithmus ja auch Merch Sort. Und dazu wird immer das erste Element
3:49 oder die ersten beiden Elemente dieser Zahlenketten verglichen und das kleinste wird aufgeschrieben. Also deswegen würde jetzt hier die drei
3:57 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.
4:06 Die drei schon mal wegstreichen. Die acht bleibt übrig. Als einzige kann ich noch dazu schreiben. Das ist also das Ergebnis hier.
4:15 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
4:22 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
4:29 aufschreiben. Dann vergleiche ich die fünf mit der vier. Da ist die vier kleiner. Kann ich auch schon mal wegstreichen.
4:37 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.
4:46 Das gleiche machen wir hier drüben auch noch mal. Die zwei und die sechs werden als erstes verglichen. Ich schreibe die zwei auf.
4:54 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.
5:02 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
5:09 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
5:18 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
5:26 entsteht jetzt unsere Zahlenfolge, so wie sie sortiert sein sollte. 7 8 und die neun. Und dadurch
5:40 und dadurch haben wir unsere sortierte Zahlenfolge erhalten. Also wir haben noch mal zwei Schritte.
5:49 Erster Schritt divide. Zweiter Schritt Conquer
6:03 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
6:13 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
6:18 geholfen. Bis zum nächsten Mal. Tschüss.