Adaptiertes 2-Phasen-2-Band-Mischen - LinkFang.de





Adaptiertes 2-Phasen-2-Band-Mischen


Dieser Artikel oder Abschnitt ist nicht ausreichend belegt.

Das 2-Phasen-2-Band-Mischen ist ein Sortieralgorithmus.

Weitere Einzelheiten

In den Anfängen der elektronischen Datenverarbeitung wurden Massendaten auf Magnetbändern abgelegt. Diese Bänder wurden mit einem Magnetkopf sequentiell gelesen und geschrieben. Es war also kein wahlfreier Zugriff möglich. Man behalf sich mit Algorithmen, die ein Band mithilfe eines zweiten (unter Umständen auch eines dritten) sequentiell sortierten.

Dieses Verfahren wurde Ende der 1990er Jahre für doppelt verkettete Listen adaptiert (Markus v. Brevern und Dirk Sorges).

Doppelt verkettete Listen bestehen aus Listenelementen, die einen Zeiger auf den Nachfolger und auf den Vorgänger besitzen. Man kann also vom Anfang vorwärts oder vom Ende rückwärts durch die Listen laufen. Einfügen und Löschen ist sehr einfach. Eine Liste ist einem Feld bei diesen beiden Operationen deutlich überlegen.

Im 2-Phasen-2-Band-Mischen werden in einer Phase Läufe (englisch runs) sortierter Elemente bestimmt. Diese Läufe werden dann in der zweiten Phase ineinander gemischt, so dass aus 2 Läufen einer wird. Der Algorithmus endet, wenn nur noch ein (jetzt vollständig sortierter) Lauf übrig bleibt.

Bei doppelt verketteten Listen verwendet man die Vorwärtszeiger als Zeiger auf das nächste Element und die Rückwärtszeiger als Zeiger auf den nächsten Lauf. Man initialisiert die Liste, indem man für jedes Element die Rückwärtszeiger wie die Vorwärtszeiger auf das nächste Element zeigen lässt. Jetzt hat man n Läufe der Länge 1. Daraufhin sortiert man so lange zwei Läufe zusammen, bis nur noch ein Lauf übrig ist. Das Sortieren erreicht man mit zwei zusätzlichen Zeigern, die jeweils auf einen Lauf zeigen. Das kleinere referenzierte Element wird in den Mischlauf übernommen, der entsprechende Zeiger auf das nächste Element des Laufs gesetzt. Ist ein Lauf ganz abgearbeitet, wird der Rest des anderen Laufs an den Mischlauf angehängt. Anhängen und Einsortieren wird einfach durch „Umzeigern“ erreicht. Abschließend werden alle Rückwärtszeiger auf das jeweils vorige Element gesetzt.

Dieses Verfahren arbeitet In-place, verbraucht also keinen weiteren Speicherplatz. Kopiert wird nichts, lediglich die Zeiger werden verändert. Der Aufwand liegt immer in O(n * log n). Es ist also das perfekte Sortierverfahren für unbestimmte Datenlagen.


Kategorien: Sortieralgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Adaptiertes 2-Phasen-2-Band-Mischen (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.