Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

37.2.2 Mergesort

37.2.2 Mergesort

Dieser Algorithmus ist schon etwas schwerer zu verstehen und kommt oft zum Einsatz, wenn Elemente in Dateien bzw. generell in externen Ressourcen, sortiert werden sollen. Die Grundidee ist folgende. Die gesamt Liste wird als eine Anzahl von ganz vielen einelementigen Listen angesehen, welche logischerweise für sich sortiert sind. Anschließend werden diese Listen immer paarweise miteinander verzahnt/vermischt, um somit größere Listen zu Erzeugen, welche wieder für sich betrachtet sortiert sind. Jene werden dann wieder paarweise verzahnt und das Ganze geht so lange, bis man nur noch eine große Liste hat.

Der Trick liegt hier in der Tatsache, dass das Verzahnen im Durchschnitt wenig vergleiche braucht, da man, sobald eine Liste vollständig Verbraten ist, den Rest der anderen ungesehen anhängen kann. Schauen Sie sich an, was ich damit meine.

Veranschaulichung des Mergesort Sortierverfahrens

Zu Beginn wird die Liste in zwei Teillisten getrennt und so lange in ihr noch mehr als ein Element ist, wird jene Teilliste wieder getrennt. Der Einfachheit habe ich die Listen einfach in der Mitte geteilt. Es finden sich aber auch Implementierungen, in welchen man immer die Elemente eins, drei, fünf usw. in die eine und die Elemente zwei, vier, sechs usw. in die andere packt. Je nach Vorsortierung, kann letztere Variante im Folgeschritt, zu weniger Vergleichen führen.

Nachdem alles geteilt wurde und somit einelementige sortierte Listen vorliegen, kann man sich an das Verschmelzen bzw. Mischen (merge) machen. Im ersten Durchlauf passiert noch nicht viel spannendes, da es lediglich auf einen Vergleich hinausläuft. Der eigentliche Algorithmus zeigt sich erst im zweiten Durchlauf.

Nachdem jetzt also u.a. die Listen [1, 6] und [2, 7] entstanden sind, kann ich Ihnen jetzt zeigen, was hinter den Kulissen passiert. Auf beide Listen verweist jetzt ein Zeiger auf das erste Element (ggf. auch einfach nur jeweils eine Variable mit einem Indexwert). Die Elemente beider Listen, auf welche verwiesen wird, werden miteinander verglichen. Der kleinere Wert wird dann in eine neue Liste kopiert und der entsprechende Zeiger (oder Index), wird anschließend um eins erhöht. Der Vergleich zwischen 1 und 2 hat also zur Folge, dass die 1 kopiert wird. Anschließend beginnt die Schleife von vorne und die 6 wird mit der 2 verglichen. Daraus resultiert, dass die 2 kopiert wird. Jetzt wird die 6 mit der 7 verglichen und die 6 wird kopiert. Nach diesem Schritt setzt der Vorteil des Verfahrens ein, obwohl er sich an dieser Stelle noch nicht so richtig zeigt. Da die erste Liste vollständig verarbeitet wurde und die zweite Liste, also [2, 7], bereits sortiert war, kann man jetzt den Rest der zweiten Liste, ungesehen kopieren. Wie gesagt, bringt das jetzt nicht viele Vorteile, da nur noch die 7 übrig geblieben ist. Was ich meine sieht man dann erst im nächsten großen Schritt.

Nachdem dann noch die Listen [3, 5] und [4] verzahnt wurden, erhält man die Listen [1, 2, 6, 7] und [3, 4, 5]. Es folgt der letzte große Schritt. Wieder wird es einen Zeiger (oder Index) auf die ersten Elemente beider Listen geben. Es folgen die Vergleiche 1 mit 3, 2 mit 3, dann 6 mit 3, 6 mit 4 und 6 mit 5. Nach diesem Vergleich ist die zweite Liste vollständig kopiert und die verbleibenden Elemente der ersten Listen, nämlich 6 und 7, können ungesehen ans Ende der resultierenden Liste kopiert werden, ohne dass noch weitere Vergleiche notwendig sind. In diesem Fall würde man also einen Vergleich sparen.

Sie werden sich jetzt vielleicht denken, dass diese Ersparnis nicht überragend ist, was aber eher an der ungünstigen Liste liegt. Dieser ungünstige Fall ist aber trotzdem genauso schnell wie Quicksort. Betrachtet man aber den Entartungsfall von Quicksort, nämlich die vorsortierte Liste, entfaltet sich das volle Potential des Mergesort Verfahrens. Der erste Schritt mit den einelementigen Listen, bringt noch keine Ersparnis, wohl aber alle Folgenden. Es werden immer zwei Listen entstehen, welche die Eigenschaft besitzen, dass alle Elemente der einen kleiner als die der anderen Liste sind. Somit benötigt man nur so viele Vergleiche, wie die die Länge einer Liste, also im Durchschnitt die Hälfte. Die Vergleiche sorgen also dafür, dass die erste Liste kopiert wird und anschließend wird die komplette andere Liste ungesehen an gehangen.

Nun habe ich wahrscheinlich den Eindruck vermittelt, dass man immer mehrere Listen, Arrays oder ggf. Dateien bentigt. Dem muss aber nicht so sein. Bereits einfachere Variationen genügen zwei Datencontainer, wobei einer immer die Quelle und einer das Zeil ist. Im folgenden Schritt, wird dann aus der Quelle das Ziel und aus dem Ziel die Quelle. Man kopiert also nur hin und her. Denkbar ist aber auch ein Algorithmus, welcher mit dem einen Container auskommt. In diesem Fall spart man dann Speicher, aber der Verwaltungsaufwand wächst so enorm, dass man langsamer als alle anderen Verfahren werden kann, da man viel mehr hin und her kopieren muss (es müssen dann ggf. Elemente bzw. sogar ganze Teile der Listen, immer um eins verschoben werden und auch die Pointer bzw. Indexwerte müssen ständig nachgepflegt werden).

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012