Algorithms and Data Structures #21 - Merge Sort: Recursive Divide and Conquer

[@sleppedasschaf7519]

Dein channel ist total underrated du hachst schon so viele gute tutorial für soviel verschiedenen programmier sprachen, IT infos, pen testing, und das alles noch kostenlos also ehre :D ich Feier deine videos einfach :) ;) ;) :) ;) :)

[@Leonardo-eu7jt]

Mittlerweile sind teilweise die Sachen zu Hacking/Sicherheit wegen dem KZbin Team leider nicht mehr gratis... :(

[@pepsiman7180]

Kommentar für den Algorithmus:))

[@flyingskillyuhu]

Dieser auch wieder ✌

[@einmensch3660]

Ohne deine Videos würde ich im Informatik Studium wohl kaum durchblicken. Bei dir kann man alles leicht verständlich lernen und in der Uni nochmal vertiefen. Dafür bin ich dir sehr Dankbar ;D

[@gnul]

Bin ich der einzige der das Alphabet nur bedingt auswendig kann? Ich habs im Gehirn nur als eine Art Linked List. :D Ab etwa ~mittig im Alphabet brauche ich 2 oder besser 3 aufeinander folgende Buchstaben gleichzeitig im RAM, erst dann habe ich den Pointer zum nächsten. Ob R vor U kommt, dafür hab ich einen Aufwand von O(indexOfLastFound). 😅 Den Index der einzelnen Buchstaben kenne ich auch nicht. Klar ich weiß, A-X kommt vor Z und sowas was man weiß, aber joa, ich muss häufig durch iterieren.

[@nayjer2576]

hahaha genau so ist es bei mir auch. L kommt vor oder nach M, kann ich so nicht sagen ^^

[@pocketrocket6604]

Tolle Videoreihe mit sehr gut erklärten Themen!

[@catsaresocute650]

Ich habe (wie immer) mich nicht getraut in der Vorlesung zu fragen, aber warum wird nicht einfach ein Zufallswert für p genommen? Das sollte ausser ganz rechts oder ganz links doch eigendlich die Sache beschleunigen? Warum ist die sortirung in so viele Schritte zerlget? Kann der Algorithmus nicht kürzer dargestellet werden als diese einzelenen Sort-Schritte in einer neuen iteration aufzurufen? Das verlängert die genutzte Zeit und Speicher nur ohne erkennbaren Nutzen (für mich)?

[@ara6123]

Hallo ich hab heute python 2.7.3 installiert aber ohne pip. pip geht bei mir nicht was soll ich machen

[@ara6123]

@Jontherippa ich habe windows

[@ara6123]

@Jontherippa danke für deine antwort ich habe aber windows

[@TheMorpheusTutorials]

du kriegst pip hierüber: pip.pypa.io/en/stable/installing/

[@ara6123]

@@TheMorpheusTutorials danke ich versuchs mal

[@ara6123]

@@TheMorpheusTutorials ich habe python 3.8.2 und python 2.7.9 und pip habe ich auch bekommen aber wenn ich pip install pygame schreibe dann ist pygame auf python 3.8.2 installiert und nicht auf python 2.7.9 why

[@spong111bob]

Muss ich im Algorithmus eigentlich einen Sonderfall schreiben, wenn zwei Elemente gleich sind (hier wenn z.B. L und L gleichzeitig geprüft werden) oder wie entscheidet der da?

[@reyanpe9505]

hallo, ich habe die gleiche Frage wie der Kollege (Ralf Kieschnick ): a) warum muss man das ganze mehrmals teilen (16->8->4->2) und nicht direkt das ganze in einer zweier Liste (liste[0]:liste[1], 3 bis 4, ...) b) wenn ich alles auf ein Element unterbreche dann habe ich doch n Operationen gemacht, oder nicht. in einer zweier Gruppe n/2. Also o(n) für das Aufteilen und nicht o(1). Oder nicht??? Beste Grüße und danke für die tolle Videos

[@nayjer2576]

a) Du müsstest von der Einzelliste eh wieder immer in Zweier zusammenpacken. Aus 2 mal 1 wird eine Zweierliste, aus zwei Zweiern dann eine Viererliste bis n.. also log(n) mal. Durch die Rekursionsaufrufe geht das Zusammenfügen dann automatisch, da die auf dem Stack von oben nach unten abgearbeitet werden. b) Ne, ähnlich wie bei a). Wenn du den iterativen Ansatz von Merge-Sort machst (also Bottom-Top), dann brauchst du auch nur O(1) um die Liste aufzuteilen, du hast ja wahlfreien Zugriff auf die Listenteile. Du kannst in einer einzigen Rechnung alles aufteilen (also 0:1, 3:4 usw..., wie du es bei a) gemacht hast)

[@nayjer2576]

ist zwar 1 jahr her vlt. hilfts jemanden aber ich hatte selbst das thema vor 2 tagen an der uni und probier mich durchzukriegen

[@maxbart1353]

ich hätte mir gelich ein beispiel dazu gewünscht

[@TheMorpheusTutorials]

Ich mach doch immer erklärung dann code momentan 😅

[@maxbart1353]

@@TheMorpheusTutorials ja, aber bitte bitte in einem video, damit das zusammen ist. aber sonst top serie.

[@maxbart1353]

@@TheMorpheusTutorials und wie wäre es mit einer KI die Bilder verändert hin zu verschiedenen Stilen (alter meister). dazu hätte ich so gern videos, falls dich das anspricht.

[@snouzz-gaming]

Frage: Wieso ist es nun Rekursive? Ist Merge-Sort ein rekursiver Suchalgorithmus? Wenn man Deide and Conquer ansieht dann ist es ja auch dann rekursive aber eigentlich nur ne for bis 1 Element da steht oder wie soll man das verstehen? Grüße

[@henning9641]

Ich habe folgendes Problem. Ich habe eine endliche Menge an Punkten in einer Fläche bestimmter Größe. Ich möchte jetzt alle Punktepaare finden, die näher zusammen liegen, als ein minimal einzuhaltender Abstand. Fertig. Ich bin bestimmt nicht der erste der dieses Problem lösen möchte & vermutlich auch nicht der Kleverste, kennt jemand eine Methode die genau das macht ? Also irgendwie kann ich das auch machen, aber ich will das extrem oft machen, sodass ich einen effektiven Weg suche. (abstand zwischen allen Punkten bestimmen und sortieren ist keine akzeptable Lösung :D ). Danke für jeden Tipp.

[@anni2410]

Wie kommt man denn von log(n) *O(1)+O(log(n)*O(n)*O(1)) zu O (log(n))* (O(n+1)), hab mir die Stelle im Video mehrmals angehört, aber es trotzdem nicht verstanden 😂 vielen Dank schonmal 😊

[@TheMorpheusTutorials]

Kommt später noch etwas genauer, wie man das abschätzt 👍

[@dickewurstfinger9093]

Ist im prinzip einfach nur ausklammern. Wenn du log n und n als variable betrachtest hast du sowas wie a + a * b = a * (1 + b)

[@sumsumcity841]

Hey morpheus ich habe eine Frage, die vielleicht etwas vorgreift. In der Vorlesung haben sie uns gesagt, dass quick sort der beste sort algorithmus ist. Da er im average case O(nlogn) hat. Doch im worst case hat er ja O(n^2) was ja ziemlich schlecht ist. Merge Sort und Heap sort haben ja beide (ich glaube in allen cases) O(n*logn). Wieso werden diese nicht mehr gebraucht? Kann es sein, da man bei Heapsort zb zuerst de Heap machen muss usw?

[@TheMorpheusTutorials]

Ich glaube das machen wir sogar direkt nächste Woche 👍

[@nayjer2576]

Ich glaube weil Merge Sort nicht in-place ist, da er zusätzlichen Speicherplatz benötigt

[@maxbart1353]

dass du am Ende ein Beispiel codest, bei jedem video der Reihe

[@Noah-wc5kl]

Kennt jemand ein gutes tool bei dem man IP Adressen präziese Orten kann?

[@LB-qr7nv]

Hier meine Lösung: #Merge Sort l1 = ["j","e","e","e","e","e","e","E","e","e","G","e","e","f","g","s","e","i","ef","l","e","s","g","y","b","f","d","l","j","a","e","r","i","h","h","a","d","p","p","k","p","ö","ü"] l2 = [7,93.8,5,41,3,-65,900,975,3702540,580,94672,1,7083,-965,2.9170,56,1083027.5,0,-1.5] l3 = [0] l4 = [chr(9786),chr(9835),chr(9787),chr(9786),chr(9824),chr(9827),chr(9834),chr(9829)] l5 = [] def erstellen(l): if l == []: l2er = [] return l2er l2er = [] for x in range(0,len(l)-1,2): if l[x] < l[x+1]: l2er = l2er + [[l[x],l[x+1]]] else: l2er = l2er + [[l[x+1],l[x]]] if len(l)%2 != 0: l2er = l2er + [[l[-1]]] return l2er def sortieren(l1, l2="##nicht_vorhanden"): l3 = [] if l2 == "##nicht_vorhanden": l3 = l1 else: while l1 != [] and l2 != []: if l1[0] < l2[0]: l3 = l3 + [l1[0]] a = (l1[0]) l1.remove(l1[0]) else: b = (l2[0]) l3 = l3 + [l2[0]] l2.remove(l2[0]) if l1 != []: l3 = l3 + l1 elif l2 != []: l3 = l3 + l2 return l3 def überlisten(l2er): länge = len(l2er) if länge == 1: return l2er[0] elif länge == 0: return [] letzte = 0 y = 0 while y < 3: lviele = [] try: for x in range(0,len(l2er),2): lviele = lviele + [sortieren(list(l2er[x]),list(l2er[x+1]))] letzte = x except IndexError: if len(l2er[0]) == 1: break if l2er[letzte] == l2er[-1]: lviele = lviele + [l2er[-1]] elif l2er[letzte+1] == l2er[-1]: lviele = lviele + [l2er[-1]] else: lviele = lviele + [sortieren(l2er[(letzte+2)],l2er[-1])] l2er = lviele if len(lviele) == 1: break lviele = lviele[0] return lviele l2er = (erstellen(l1)) print(überlisten(l2er)) l2er = (erstellen(l2)) print(überlisten(l2er)) l2er = (erstellen(l3)) print(überlisten(l2er)) l2er = (erstellen(l4)) print(überlisten(l2er)) l2er = (erstellen(l5)) print(überlisten(l2er)) Noch nicht perfekt, aber schon recht schnell Edit: Danke Morpheus, deine Videos sind wirklich sehr gut

[@Adlerwacht]

Bitte weniger Füllworte verwenden (äh, so, quasi, sozusagen, Endeffekt). Das ist eine Seuche und nervt.

[@hyde_stopStealingMyUsername]

lappen