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 Schnelle Sortierverfahren

37.2 Schnelle Sortierverfahren

Wie bereits erwähnt, muss man oft mehrere Elemente doppelt vergleichen, obwohl das Ergebnis eigentlich rein logisch schon klar ist. Insertionsort hat dieses Problem schon ganz gut umschifft, aber es geht noch besser. Schnelle Algorithmen haben im Durchschnitt eine Komplexität von n log(n). Dies bedeutet, dass man die Verfahren wieder auf jedes Element in der Liste anwenden muss, aber jetzt fast immer nur noch die Hälfte der restlichen Elemente verglichen wird oder sogar noch weniger. Das einmal für jedes Element, wird durch das n ausgedrückt und das weniger oder genau die Hälfte, wird mittels des Logarithmus beschrieben.

Zum Seitenanfang
Zum Inhaltsverzeichnis

37.2.1 Quicksort

37.2.1 Quicksort

Fangen wir als erstes mit Quicksort an, da jenes noch relativ einfach zu verstehen ist und auch das Gebräuchlichste ist. Das Grundprinzip ist, dass ich meine Liste Teile und in die eine alle kleinen Elemente packe und in die andere alle großen. Somit hab ich hab ich schon einmal grob sortiert. Man kann sich das wie ein Sieb vorstellen. Anschließend wird dieses Prinzip auf die 2 Listen angewandt, was zur Folge hat, dass die Liste mit kleinen Elementen in eine Liste mit winzigen und in eine mit relativ kleinen Elementen geteilt wird, wohingegen die Liste der großen in mittelgroße und ganz große geteilt wird und so weiter und sofort. Dies wird so lange gemacht, bis man nur noch Teillisten hat, die nur noch ein Element besitzen. Wie wird das aber im einzelnen realisiert? Hier wieder eine Grafik.

Veranschaulichung des Quicksort Sortierverfahrens

Zuerst wird ein s.g. Pivotelement bestimmt, was üblicherweise immer das Letzte ist, also im ersten Schritt die 4. Jetzt wird "gleichzeitig" von vorne, nach größeren Elementen gesucht und von hinten, nach kleineren. Sobald jeweils ein größeres und ein kleineres gefunden wird, werden sie vertauscht. Dies wird so lange gemacht, bis sich die zwei Suchpositionen überlappen. Jetzt ist die Liste also für die Teilung vorbereitet und es wird nur noch das Element an der Stelle der Überlappung mit dem Pivotelement getauscht, also die 7 mit der 4. Nun wird Quicksort für die Liste [3, 1, 2] und die Liste [5, 6, 7] aufgerufen.

Beim ersten Unteraufruf von Quicksort, wird die 2 pivotisiert und alles was davor steht wieder für eine Teilung vorbereitet. Dies hat zur Folge, dass die 1 mit der 3 getauscht werden und da sich die Suchpositionen dann überlappen, wird die 3 mit der 2 getauscht. Jetzt wird wieder Quicksort für die Listen [1] und [3] aufgerufen, was zur Folge hat, dass hier abgebrochen wird, da Listen mit einem Element sortiert sind. Der Linke Teil der gesamten Liste ist jetzt sortiert, da Pivotelemente immer an der richtigen Stelle stehen und somit den sortierten Bereich darstellen (auch wenn er zerpflückt ist). Jetzt wird der Spaß ja noch für die Liste [5, 6, 7] durchgeführt und hier sieht man auch gleich sehr schön den Nachteil von Quicksort. Da die Liste eigentlich schon sortiert ist, wird kein Element mehr gefunden, welches größer ist als das Pivotelement, was zur Folge hat, dass Quicksort für die Liste [5, 6] aufgerufen wird, wo wieder das selbe Problem auftritt.

Im aller schlimmsten Fall braucht Quicksort also auch quadratische Laufzeit in seiner Standardimplementierung. Allerdings hat man schon einige Ideen entwickelt, um diesen Entartungsfall einer vor sortierten Liste, zu begegnen. Ein Ansatz ist das Prinzip der verbesserten Pivotisierung. Hier wird nicht einfach das letzte Element genommen. Außerdem kann man für kleine Teillisten auch Insertionsort benutzen. Ich hab ja gesagt, dass die Algorithmen bei relativ wenigen Elementen keinen spürbaren zeitlichen Unterschied machen. Zudem nimmt man Insertionsort, weil es genau mit diesem "bösen"> Fall, besonders gut, nämlich linear, umgehen kann.

Allerdings hat Quicksort trotzdem noch ein großen Pferdefuß. Mit jedem Durchlauf werden ja rekursiv, zwei weitere Quicksortfunktionen aufgerufen, welche wiederum jeweils zwei aufrufen. Dies hat zur Folge, dass es nicht lange dauert, bis man einen Stackoverflow verursacht, da ein Rechner nicht mit unendlich vielen Aufrufen von Subroutinen umgehen kann. Man kann dem zwar entgegen kommen, in dem man wie erwähnt für kleine Teillisten Insertionsort benutzt und somit keine weiteren Aufrufe hat, allerdings hilft dies bei spätestens Zehnmillionen Elementen, auch nichts mehr. Aus diesem Grund hat man s.g. iterative Quicksortalgorithmen "erfunden", welche statt Aufrufe von Subroutinen, sich entsprechende Teilbereiche in Hilfslisten speichert. Man verlagert dadurch das Problem lediglich vom Stack auf den Heap. Nun ist der Heap um einiges größer, weshalb man mehr Luft hat, aber auch hier gibt es Hardware bedingte Grenzen und auf den Heap kann man nicht ganz so schnell zugreifen, da Indirektionen durch Pointer hinzukommen.

Im Anhang finden Sie einmal das einfache Quicksort und zudem das optimierte Verfahren mit der verbesserten Pivotisierung und Insertionsort. Auf den iterativen Algorithmus habe ich verzichtet. Aber die Umbauten dafür wären nicht so Problematisch. Sie bräuchten wie gesagt lediglich eine Liste, welche Positionen halten kann und eine große Schleife, welche so lange arbeitet, bis nichts mehr in der Liste steht. Statt dann zwei mal die Quicksortfunktion mit den Positionen der Teilbereiche aufzurufen, speichern Sie diese Teilbereiche einfach in der Liste (vorausgesetzt der Teilbereich ist größer als eins) und fertig.

Zum Seitenanfang
Zum Inhaltsverzeichnis

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

37.2.3 Heapsort

37.2.3 Heapsort

Das letzte Sortierverfahren welches ich besprechen werde, ist meiner Meinung nach das komplizierteste, da man nicht wirklich auf Anhieb sieht, warum dieser Algorithmus funktioniert. Aber da ich Ihnen auch mal andere Herangehensweisen zeigen möchte, habe ich es mit aufgenommen.

Die Grundidee ist, dass man die Liste als ein Binärbaum betrachtet, also ein Baum mit einer Wurzel bzw. einem Vaterknoten und zwei Kindern. Jener Baum wird dann immer so modifiziert, dass der Vater größer ist als beide Kinder und das linke Kind größer ist als das rechte. Dies nennt man "MaxHeapify". Damit sorgt man dafür, dass das größte Element am Anfang der Liste steht. Jenes wird dann mit dem letzten Element der unsortierten Liste vertauscht, was zur Folge hat, dass es quasi vor den Sortierten Bereich gehangen wird. Das selbe Spiel wird dann mit der um eins verkleinerten Liste gemacht.

Nun wird aber kein wirklicher Baum erzeugt, da der Verwaltungsaufwand zu groß und somit das Verfahren nicht effizient wäre. Die Vorbereitungen und das eigentliche Sortieren, werden alle im Ausgangscontainer vorgenommen. Jener wird nur rein logisch wie ein Baum behandelt. Dies ist auch garnicht schwer, wenn man es mit einem Binärbaum zu tun hat. Es wird einfach davon ausgegangen, dass das erste Element die Wurzel ist und die Kinder eines jeden Vaters, stehen an der Position des Vaters mal zwei, bzw. mal zwei plus eins. So hat die Wurzel "eins" die Kinder "zwei" und "drei" (1 x 2 = 2 und 1 x 2 + 1 = 3). Der Vater "zwei", hat die Kinder "vier" und "fünf" (2 x 2 = 4 und 2 x 2 + 1 = 5). Sie sehen also, dass dieses Verfahren sehr gut funktioniert. In den folgenden Grafiken werde ich immer Bäume aufmalen, damit Sie besser sehen, was passiert.

Bevor das Sortierverfahren losgehen kann, muss aus der Liste ein Ausgangsheap erzeugt werden. Dies nennt man "BuildMaxHeap". Dies sieht wie folgt aus.

Vorbereitungen für Heapsort

Die Liste wird von hinten Durchlaufen und aus den Elementen zwischen Position und Ende, die Heapeigenschaft hergestellt. Es wird jeder Vater (vom Untersten an) mit dem untersten Kind verglichen und ggf. vertauscht, falls das Kind einen größeren Wert hat. Dies alleine sorgt zwar nicht dafür, dass dieser Teil komplett richtig ist, aber falls Fehler entstehen, wie man das bei der Teilliste [2, 5, 3, 4] sieht, so werden jene im nächsten Schritt automatisch korrigiert. Dies liegt daran, dass im nächsten Schritt die Elemente ganz anders interpretiert werden (aus Blättern können Knoten werden und umgekehrt).

Das Vorbereiten der Liste dauert am längsten (lineare Laufzeit), aber die Vorbereitungen sorgen dann später dafür, dass im Schnitt nur noch die Hälfte überprüft werden muss, da ein Baum entsteht, welcher den Anforderungen entspricht. Nun kann das eigentliche Sortieren beginnen. In folgender Grafik sehen Sie den ersten Durchlauf.

Erster Sortierschritt des Heapsort Verfahrens

Am Anfang eines jeden Durchlaufes, wird wie erwähnt, das erste Element mit dem letzten Vertauscht. Am Anfang stellt genau jenes Element das größte in der gesamten Liste dar. Die 7 wird also mit der 2 getauscht und kann als sortiert betrachtet werden. Jetzt ist allerdings die Heapeigenschaft für den unsortierten Bereich nicht mehr gegeben und deswegen wird "MaxHeapify" aufgerufen. Die Grundidee ist hier, dass der Baum hauptsächlich oben kaputt ist (weil dort ja was vertauscht wurde) und jetzt ein paar kleinere Korrekturen vorgenommen werden müssen. Die Wurzel wird also mit seinen Kindern verglichen und es wird ggf. etwas getauscht. In meinem Beispiel die 2 mit der 6. Jetzt muss noch gewährleistet werden, dass das linke Kind größer ist als das rechte. Ggf. muss wieder getauscht werden, was in meinem Beispiel dazu führt, dass die 2 mit der 5 getauscht wird. Jetzt folgt ein sehr theoretischer Ansatz. Man geht davon aus, dass, wenn ein Teil des Baumes den Heapeigenschaften genügt, alle darunter liegenden Unterbäume, auch jenen Eigenschaften genügen. Es wird also erst geprüft, ob der Vaterknoten 5 größer ist als 4 und 1 und ob die 4 größer ist als die 1. Ist dem so, muss nichts weiter gemacht werden. Aus Gründen der Übersichtlichkeit, ist die Liste nur verhältnismäßig klein, sodass ich jetzt nicht so richtig deutlich machen kann, dass hier wirklich nichts mehr gemacht werden muss. Aber hingen Theoretisch unter der 4 und der 1 weitere Bäume, so bräuchte da nichts gemacht werden, was zur Folge hat, dass man sich grob gesagt, um die Hälfte der Elemente nicht mehr kümmern muss. Nun muss nach das zweite Kind, also die 2 und ihre Kinder, kontrolliert werden. Dies hat zur Folge, dass die 2 mit der 3 getauscht wird. Da die 2 jetzt neues Kind ist und somit für alle Unterbäume die Heapeigenschaft nicht mehr stimmen könnte, wird hier nochmals geprüft. Da die 2 ebenfalls ein Blatt ist, ist dieser Schritt beendet.

Zweiter Sortierschritt des Heapsort Verfahrens

Jetzt geht der ganze Spaß von vorne los. Das erste Element wird wieder mit dem letzten Element des unsortierten Bereiches vertauscht, was zur Folge hat, dass die 6 vor den sortierten Bereich, also die 7, kommt. Nun wird wieder der Baum "aufgebaut" und von oben her geschaut, ob was getan werden muss. Die 2 wird also mit der 5 getauscht. Da die 2 jetzt nicht gröer ist als ihre Kinder, wird wieder getauscht und so landet die 4 eine Ebene weiter oben. Da die 4 größer ist als ihr rechter Bruder. Ist wieder Feierabend. Warum wurde aber jetzt erst der Unterbaum repariert und dann erst mit dem Bruder verglichen? Vorhin war es doch anders herum! Dies ist immer abhängig von der Anzahl und der Verteilung der Elemente im Baum und ist der Tatsache verschuldet, dass ich keinen richtigen Baum, sondern eine habe. Je nach Längen der Liste, wird bei gerader Anzahl der Elemente, erst der Brudervergleich vorgenommen, bzw. bei ungerader Länge, erst der Kindvergleich.

Dritter Sortierschritt des Heapsort Verfahrens

Nachdem die Heapeigenschaft erneut wiederhergestellt ist, geht das Spiel nochmals von vorne los. Wieder der Tausch des ersten mit dem letzten Element vorgenommen und "MaxHeapify" aufgerufen. Hier sehen Sie wieder schön, dass jetzt erst der Bruder verglichen wird, obwohl man auch erst die 1 mit der 2 tauschen könnte.

Ich denke, jetzt sollte so ungefähr klar sein was passiert und wenn nicht, dann ist dies nicht so schlimm, da dieses Verfahren wie Shellsort, eher selten benutzt wird. Der Vollständigkeit halber sehen Sie jetzt noch die drei letzten Schritte.

Vierter Sortierschritt des Heapsort Verfahrens

Fünfter Sortierschritt des Heapsort Verfahrens

Sechster Sortierschritt des Heapsort Verfahrens

Abschließend sei noch erwähnt, dass die Reparatur immer nur in dem Teilbaum durchgeführt werden, welcher den kleineren Vater hat. Somit betrachtet man erst die Hälfte, dann nur noch ein Viertel, dann ein Achtel und so weiter. Es kommt dann lediglich noch der Vergleich des Bruders hinzu. Wir haben also auch logarithmische Laufzeit. Allerdings braucht man in der Regel mehr vergleiche als bei den vorhergehenden Verfahren, was diesen Sortieralgorithmus in der Praxis unattraktiv macht.

Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012