Diskussion:Adaptiertes 2-Phasen-2-Band-Mischen

Sortieraufwand

Wie in Sortierverfahren bewiesen ist, ist der minimale Aufwand für das Sortieren $O(nlogn)$. Dies gilt auch für dieses Verfahren, da der Aufwand für das Mischen $O(n+m)$ ist, wobei n und m die Länge der beiden Läufe sind. Es finden $logn$ Merge-Operationen statt, so dass der Aufwand insgesamt $O(nlogn)$ sein sollte.
(Der vorstehende Beitrag stammt von 82.83.174.179 – 22:18, 14. Mär. 2005 (MEZ) – und wurde nachträglich unterschrieben.)

Felder und Listen (erl.)

"Einfügen und Löschen ist sehr einfach. Daher ist eine Liste einem Array sehr überlegen." Ne, nicht wirklich. Zuerst einmal ist ein Array selber schon eine Liste. Die Rede hier ist von einer verketteten Liste und man muss sich schon sehr genau ausdrücken, bei welchen Operationen sie überlegen ist.
(Der vorstehende Beitrag stammt von 84.150.44.236 – 16:36, 1. Okt. 2005 (MESZ) – und wurde nachträglich unterschrieben.)

Danke für den Hinweis, der betreffende Satz wurde entsprechend ergänzt,^[1] womit dieser Abschnitt hier wohl erledigt sein dürfte. MfG, 92.231.185.180 08:14, 27. Mär. 2013 (MEZ)

Wie Mergesort?

Verstehe ich das richtig, dass der Algorithmus wie Mergesort abläuft, nur dass schon sortierte teillisten nicht mehr getrennt werden? 129.13.186.1 22:07, 20. Jun. 2008 (CEST)

Der Algorithmus ist ähnlich dem Natürlichen Mergesort. Es ist jedoch kein einleitender Schritt nötig, Runs zu finden. Jedes Element ist initial ein Run mit einem Element. Der entscheidende Unterschied ist aber, dass ausschließlich Pointer verändert werden. Der Algorithmus arbeit also wirklich 100% in-place (er verbraucht nicht nur einfach keinen zusätzlichen Speicherplatz, sondern lässt alle Elemente da, wo sie sind). Damit ist dieses Sortierverfahren auf natürliche Weise dem Typ der doppelt verketteten Liste angepasst und verzichtet von vornherein auf eine Anwendbarkeit auf Arrays. (Markus v. Brevern, 30. November 2008)

(Der vorstehende Beitrag stammt von 87.79.71.187 – 21:24, 30. Nov. 2008 (MEZ) – und wurde nachträglich unterschrieben.)

Literatur

bevor noch jemand auf die idee kommt, das "buch" Adaptiertes 2-Phasen-2-Band-Mischen einzufuegen: "Please note that the content of this book primarily consists of articles available from Wikipedia or other free sources online." [2] --Mario d 23:04, 26. Mär. 2013 (CET)

Und in der hier üblichen Sprache (also auf Deutsch, frei übersetzt): Bitte beachten Sie, daß der Inhalt dieses Buches im Wesentlichen aus Artikeln besteht, die aus der Wikipedia stammen oder in anderen freien Quellen (im Netz) verfügbar sind. (mit Hilfe des Google-Übersetzers) Und Mario, unterlasse es bitte künftig, in dieser Form (siehe [3]) die Beiträge anderer Mitarbeiter einfach zurückzusetzen, so daß auch andere Änderungen entfernt werden, die mit d(ein)er Sache nichts zu tun haben. Im Übrigen ist die Zusammenfassungszeile nicht für Fragen oder Diskussionen vorgesehen, sondern eben diese Seite hier (siehe auch Hilfe:Zusammenfassungszeile und Hilfe:Diskussionsseiten). MfG, 92.231.185.180 08:14, 27. Mär. 2013 (MEZ)

ich habe einen beitrag zurueckgesetzt, der offensichtlich ungeeignete "literatur" eingefuegt hat. in dem beitrag gab es bis auf ein bischen quelltextkosmetik keine anderen aenderungen. bevor du hilfeseiten verlinkst, solltest du dich mal an die eigenen nase fassen: "Wer Literatur in einem Artikel angibt, sollte diese zuvor selbst eingesehen haben." (WP:Lit) --Mario d 14:05, 27. Mär. 2013 (CET)

Es gibt keinen externen Beleg. Das Verfahren stammt von mir und ist hier im ORIGINAL erklärt. Es ist von Sinn her ein Verfahren, das mit zwei Bändern laufen könnte, es gibt zwei Phasen und es ist nicht mit Bändern gelöst, sondern mit doppelt verketteten Listen, also ist es adaptiert. Der Source-Code ist in C++ 132 Zeilen lang, inkl. Kommentare. (Markus v. Brevern, 29. April 2014 19:55) (ohne Benutzername signierter Beitrag von 92.50.72.93 (Diskussion))