Ich habe ein Video "nur" in der TH-cam Suche gefunden. Dann auf den Kanal geklickt und allein das "sichten" der Videos hat mich zum Abo Button innerlich gedrängt. Jetzt nachdem ich das MergeSort Video gesehen habe bin *unglaublich* begeistert! Ich habe bisher nicht eine so gut und so anschauliche Erläuterung und Erklärung über einen Sortieralgorithmus gesehen, wie in diesem Video. Ich bin mir jetzt schon sicher das die anderen Videos genauso gut sind. Eine wirklich vergleichlose Arbeit - auf jeden Fall im deutschsprachigen Raum. Vielen dank für ihre Videos! Sie haben meinen größten Respekt! Toll!🥳
In welchem Video finde ich die Erklärung wieso die Laufzeit O(n * log n ) ist? Tolle Arbeit die sie hier hochladen, die Videos sind eine riesige Hilfe!
Vor allem kann man Mege-Sort in einer verketteten Liste auch ohne Performance-Verlust bis auf den des Pointer-Chasings (kein funktionierender Prefetch mehr durch die CPU und OoO-Serialisierung) durchführen. Man lässt die linke und rechte Rekursion eben nur jeweils den Anfang der eigenen Krette an den Aufrufer zurückgeben. Ich hab das mal gemacht und bin dabei einen hybriden Weg gegangen bzw. habe jeweils eine Kette von "Pages" gebildet die jeweils 1kB groß waren; das macht die Allokation duch Pooling dieser Pages recht einfach und schnell. Innerhalb der Pages habe ich dann den Vorteil linearer Zugriffe, also dass mehrere Elemente des "Arrays" ggf. in den selben Cachezeilen liegen und die CPU die fortlaufenden Zugriffe erkennen kann und innerhalb so einer Page dann auch Prefetching durchführen kann.
Der Clou ist, dass die Sortierung der halben Arrays über rekursive Aufrufe von MergeSort selbst läuft, d.h. die Teilarrays werden ihrerseits wieder geteilt, diese dann wieder usw.. Das endet erst, wenn das Array vollständig zerlegt ist.
Sort Algorithmen sind schon interessant, versuche gerade diese in C# mit Windows Forms mit Panel zu zeigen , hat bisher mit Bubble, Quick, Selection und Insertion funktioniert, aber bei Merge fällt es mir schwer die Positionen der Panels zu verändern.
Klingt interessant. Leider kenne ich mich mit Windows Forms gar nicht aus. Was genau ist denn das Problem bei Merge im Vergleich zu anderen Algorithmen?
Tatsächlich benutzen wir ja im Algorithmus Merge zwei Arrays, nämlich a und b. Die Frage ist vermutlich, warum wir das Ergebnis nicht einfach im zweiten Array b belassen, sondern die Werte am Ende noch umständlich nach a zurück kopieren. Bitte bedenken Sie aber, dass man Merge mehrmals in verschiedenen Rekursionsebenen aufruft. Damit das dann noch alles korrekt funktioniert, müsste man ein wenig tricksen: In jeder zweiten Ebene sortiert man die Werte z.B. von a nach b und in den restlichen Ebenen die Werte von b nach a. Wenn man das schafft, kann man MergeSort tatsächlich ziemlich schnell machen. Insgesamt wird der Algorithmus dadurch aber komplizierter; darum habe ich mich hier dafür entschieden, einfach b nach a zu kopieren.
Ich habe ein Video "nur" in der TH-cam Suche gefunden. Dann auf den Kanal geklickt und allein das "sichten" der Videos hat mich zum Abo Button innerlich gedrängt. Jetzt nachdem ich das MergeSort Video gesehen habe bin *unglaublich* begeistert! Ich habe bisher nicht eine so gut und so anschauliche Erläuterung und Erklärung über einen Sortieralgorithmus gesehen, wie in diesem Video. Ich bin mir jetzt schon sicher das die anderen Videos genauso gut sind.
Eine wirklich vergleichlose Arbeit - auf jeden Fall im deutschsprachigen Raum. Vielen dank für ihre Videos! Sie haben meinen größten Respekt! Toll!🥳
Vielen Danke für das positive Feedback! :)
Absolut Klasse gemacht. Der gesamte Kanal ist so extrem hilfreich. Vielen dank:)
Hihi ich bin so froh, dass ich mir letztes Jahr so viel Mühe gegeben habe, sodass ich Sie weiterhin als Professor habe - Sie machen das toll x)
Sie retten mein Studium! Danke vielmals:D
In welchem Video finde ich die Erklärung wieso die Laufzeit O(n * log n ) ist? Tolle Arbeit die sie hier hochladen, die Videos sind eine riesige Hilfe!
Tolle Erklärung!
Vor allem kann man Mege-Sort in einer verketteten Liste auch ohne Performance-Verlust bis auf den des Pointer-Chasings (kein funktionierender Prefetch mehr durch die CPU und OoO-Serialisierung) durchführen. Man lässt die linke und rechte Rekursion eben nur jeweils den Anfang der eigenen Krette an den Aufrufer zurückgeben. Ich hab das mal gemacht und bin dabei einen hybriden Weg gegangen bzw. habe jeweils eine Kette von "Pages" gebildet die jeweils 1kB groß waren; das macht die Allokation duch Pooling dieser Pages recht einfach und schnell. Innerhalb der Pages habe ich dann den Vorteil linearer Zugriffe, also dass mehrere Elemente des "Arrays" ggf. in den selben Cachezeilen liegen und die CPU die fortlaufenden Zugriffe erkennen kann und innerhalb so einer Page dann auch Prefetching durchführen kann.
echt krass,danke sehr
ich dachte der mergesort zerlegt in atomare Teile? Hier hingegen haben wir nur zwei halbe arrays? Was übersehe ich?
Der Clou ist, dass die Sortierung der halben Arrays über rekursive Aufrufe von MergeSort selbst läuft, d.h. die Teilarrays werden ihrerseits wieder geteilt, diese dann wieder usw.. Das endet erst, wenn das Array vollständig zerlegt ist.
18:30 wäre es dann nicht if (ilinks
i_l darf bis m-1 laufen, also entweder "if (i_l
Sort Algorithmen sind schon interessant, versuche gerade diese in C# mit Windows Forms mit Panel zu zeigen , hat bisher mit Bubble, Quick, Selection und Insertion funktioniert, aber bei Merge fällt es mir schwer die Positionen der Panels zu verändern.
Klingt interessant. Leider kenne ich mich mit Windows Forms gar nicht aus. Was genau ist denn das Problem bei Merge im Vergleich zu anderen Algorithmen?
warun einfach das gleiche Array benutzen `? es wäre doch weniger Bedingungen stehen , wenn wir richtig 2 unter Arrays hätten...
Tatsächlich benutzen wir ja im Algorithmus Merge zwei Arrays, nämlich a und b. Die Frage ist vermutlich, warum wir das Ergebnis nicht einfach im zweiten Array b belassen, sondern die Werte am Ende noch umständlich nach a zurück kopieren. Bitte bedenken Sie aber, dass man Merge mehrmals in verschiedenen Rekursionsebenen aufruft. Damit das dann noch alles korrekt funktioniert, müsste man ein wenig tricksen: In jeder zweiten Ebene sortiert man die Werte z.B. von a nach b und in den restlichen Ebenen die Werte von b nach a. Wenn man das schafft, kann man MergeSort tatsächlich ziemlich schnell machen. Insgesamt wird der Algorithmus dadurch aber komplizierter; darum habe ich mich hier dafür entschieden, einfach b nach a zu kopieren.
🤣🤣🤣🤣🤣😂😂🤣🤣🤣