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...

I Sortieren und Suchen

I Sortieren und Suchen

Zum Seitenanfang
Zum Inhaltsverzeichnis

38 Die geläufigsten Suchverfahren

38 Die geläufigsten Suchverfahren

Eine weitere seht häufige auftretende Thematik in der Informatik, ist das Auffinden von Elementen in einem Array oder einer Listen. Auch hierfür gibt es wieder verschiedenste Ansatzmöglichkeiten, welche ich aber nur theoretisch anschneiden werde, damit Sie auch davon mal etwas gehört haben. Eine schnelle Suche setzt allerdings immer eine Vorsortierung der Liste voraus. Wie man dafür sogt, habe ich Ihnen ja im letzten Kapitel gelzeit.

Zum Seitenanfang
Zum Inhaltsverzeichnis

38.1 Einfache lineare Suche

38.1 Einfache lineare Suche

Der trivialste Fall um ein Element zu finden, ist die gesamte Liste, Schritt für Schritt, durchzulaufen, bis man das gewünschte Element gefunden hat. Dies nennt man lineare Suche und wie Sie sich schon denken können, hat jene eine Laufzeit von n, da man im schlimmsten Fall, jedes Element besuchen muss.

Lineare Suchen machen nur dann Sinn, wenn man unsortierte Listen hat, weil der Sortieraufwand zum einen teurer wäre (angenommen ich will nur einmalig was suchen) oder weil man überhaupt kein Kriterium für die Sortierung hat (angenommen man hat eine Liste mit verschiedenen Objekten, die nichts gemeinsam haben, nur gemeinsam verwaltet werden, wie z.B. alle Steuerelemente eines Fensters, also Eingabefelder, Buttons usw. - nach was soll man jene sinnvoll sortieren?) oder weil man die Elemente nicht sortieren darf um die Semantik nicht zu verletzen (es wäre unklug einen Text zu sortieren um ein Wort zu finden). Sobald man aber die Liste sortieren kann und mehrfach Elemente sucht, rechnet sich irgendwann die einmalige Vorsortierung.

Zum Seitenanfang
Zum Inhaltsverzeichnis

38.4 Interpolierende Suche

38.4 Interpolierende Suche

Dieses Verfahren versucht nun folgende Problematik zu umgehen. Angenommen Sie suchen in New York, eine Person mit dem Nachnamen "Zwicker" im Telefonbuch. Nach dem Intervallhalbierungsverfahren, müssten Sie das Buch in der Mitte aufschlagen, dann vom Rest noch einmal die Hälfte und so weiter und so weiter. Somit brauchen Sie trotzdem relativ lange, um ein Element am Ende einer Liste zu finden. Wenn man sich aber selber mal beobachtet, dann sucht man in einem Telefonbuch anders. Man schlägt gleich den Teil auf, in welchem Namen mit Z stehen und dann sucht man nach "Zw", was erheblich schneller geht. Genau dies wird durch dieses Verfahren annähernd realisiert. Bei der Interpolation wird quasi eine bessere "Mitte" geschätzt, so dass man die Liste nicht teilt, sondern drittelt, viertelt oder sogar in einen noch kleineren Bereich teilt.

Dummerweise funktioniert dieses Verfahren aber nicht bei Texten, sondern nur bei Zahlen und dann auch nur, wenn die Zahlen verhältnismäßig gleich verteilt sind. Der Grund ist folgender. Es wird vom ersten und letzten Element der Betrag gebildet und die Länge des Bereiches ermittelt. Anschließend wird eine Art Prozentwert für das zu suchende Element gebildet, welcher der tatsächlichen Position entspricht oder ihr sehr nahe kommt. Stimmt die Position noch nicht, wird der Bereich verkleinert und der Spaß beginnt von vorne. Folgende Grafik wird dies an einem konkreten Beispiel demonstrieren.

Veranschaulichung der interpolierenden Suche

In diesem Beispiel wird das zu suchende Element, bereits im ersten Durchlauf gefunden. Wäre dies nicht der Fall, würde geprüft werden, ob die neue Mitte kleiner oder größer ist, als das zu suchende Element. In dem Fall das es größer ist, wird die linke Grenze auf Mittelwert plus eins gesetzt und im Fall das es kleiner ist, wird die rechte Grenze auf Mittelwert minus eins gesetzt. Entspricht die linke und die rechte Grenze nicht dem gesuchten Wert, wird wieder die Formel angewandt.

Zum Seitenanfang
Zum Inhaltsverzeichnis

38.2 Verbesserte lineare Suche

38.2 Verbesserte lineare Suche

Gerade dann, wenn es sich um Texte handelt, die man nicht sortieren darf, braucht man eine schnellere Möglichkeit, als das Suchwort an den Anfang des Textes anzulegen und dann immer Zeichenweise weiter zu verschiebt, um dann immer die Komplette Zeichenkette zu vergleichen. Gerade bei sehr sehr langen Texten und langen Suchwörtern, würde dies extrem lange dauern. Deswegen möchte ich Ihnen hier den Boyer-Moore-Algorithmus vorstellen, welcher sehr viel schneller das gesuchte Wort findet.

Die Grundidee ist, dass man am Anfang, das zu suchende Wort an den Text anlegt und den letzten Buchstaben mit dem Buchstaben vergleicht, der im Text an dieser Stelle steht. Wenn es eine Übereinstimmung gibt, wird der Buchstabe davor verglichen und wenn es wieder eine Übereinstimmung gibt, wird der Buchstabe davor betrachtet. Wenn alle Buchstaben übereinstimmen ist die Position gefunden. Sobald der Vergleich fehlschlägt, wird geprüft, ob der Buchstabe des Textes im Suchwort vorkommt. Ist dies nicht der Fall, wird das Suchwort um seine Länge verschoben und der Algorithmus beginnt von vorne. Ist der Buchstabe im Suchwort enthalten, wird die Differenz aus der Position des hintersten vorkommenden Buchstabe (vor dem Bereich in welchem es Übereinstimmungen zum Text gab) mit der Position der letzten Übereinstimmung ermittelt und das Suchwort um diese Anzahl verschoben. Da dies jetzt sehr theoretisch klingt, werde ich dies an einem kleinen Beispiel zeigen.

Veranschaulichung des Boyer-Moor-Algorithmus

Im Ersten Schritt wird also das a aus dem Text, mit dem a aus dem Suchwort verglichen und eine Übereinstimmung festgestellt. Dies hat zur Folge, dass das l mit dem r verglichen wird und da sich diese zwei Buchstaben unterscheiden, wird jetzt nach dem hintersten l im Suchwort, vor "ra", linear gesucht. Zwei Positionen weiter vorne, wird jetzt ein l gefunden und somit wird das Suchwort um zwei verschoben.

Im nächsten Schritt wird jetzt das i aus dem Text, mit dem a aus dem Suchwort verglichen. Da es nicht übereinstimmt und das i nicht im Suchwort vorkommt, wird das Suchwort um seine gesamte Länge verschoben.

Der Rest sollte jetzt klar sein und wie Sie sehen, benötigt man weniger Schritte, als würde man das Wort immer Zeichen für Zeichen verschieben und alles Prüfen.

Zum Seitenanfang
Zum Inhaltsverzeichnis

38.3 Logarithmische Intervallhalbierungsverfahren

38.3 Logarithmische Intervallhalbierungsverfahren

Dieses Verfahren sollte Ihnen vieleicht noch aus dem Mathematikunterricht, unter dem Namen "Newtonsches Intervallhalbierungsverfahren", kennen. Es wird In einer sortierten Liste das mittlere Element benommen und mit dem gesuchten verglichen. Ist das gesuchte Element größer, dann wird aus dem hinteren Teil das mittlere Element genommen und mit dem zu suchenden Verglichen. Somit bewegt man sich in dieser Liste, ähnlich wie in einem Binärbaum und somit ist die Suchdauer nur von der Höhe abhängig, also in logarithmischer Zeit zu bewältigen.

Veranschaulichung des Intervallhalbierungsverfahrens

Zum Seitenanfang
Zum Inhaltsverzeichnis

37 Die geläufigsten Sortierverfahren

37 Die geläufigsten Sortierverfahren

In jedem Bereich der Informatik kommt man früher oder später an den Punkt, an welchen man Daten sortieren muss. An dieser Stelle werde ich die Sortierung nur theoretisch besprechen und werde dazu immer das Zahlenbeispiel [6, 1, 7, 2, 5, 3, 4] benutzen. Entsprechende Quelltexte zur Implementierung der Verfahren, finden Sie im Anhang. Jene werden (abgesehen von den Kommentaren) nicht weiter erklärt und wurden als Template entworfen, damit man möglichst flexibel ist.

Prinzipiell arbeitet jedes Sortierverfahren nach einer Grundlegenden Philosophie. Sie nennt sich "Teile und Herrsche". Was ist damit gemeint? Nun, man versucht immer einen Teil einer Liste oder eines Arrays so zu organisieren, dass er sortiert ist. Anschließend wird das Verfahren auf den unsortierten Teil angewendet und dessen sortierter Bereich irgendwie mit dem zuvor sortierten Bereich verschmolzen/verkettet. Dies geschieht auf mehr oder weniger gute Art und Weise, was verschiedene Laufzeiten zur Folge hat.

Als Hinweis sei an dieser Stelle schon einmal gesagt, dass es prinzipiell mehrere Betrachtungsweisen der folgenden Algorithmen gibt und von daher werden kommende Beschreibungen teilweise von anderen Quellen abweichen. Dies liegt daran, dass es immer drauf ankommt, ob man aufsteigen oder absteigend sortiert. Des weiteren kann man besagten sortierten Bereich am Anfang der Liste organisieren oder auch am Ende. Dies hat zur Folge, dass die Verfahren entsprechend ihrer Herangehensweise, die Listen entweder immer von Vorne oder von Hinten durchlaufen werden. Wenn Sie also irgendwann mal abweichende Implementierungen oder Erklärungen sehen, dann werden Sie feststellen, dass jener die gleiche Idee zu Grunde liegt.

Zum Seitenanfang
Zum Inhaltsverzeichnis

37.1 Langsame Sortierverfahren

37.1 Langsame Sortierverfahren

Wie bereits erwähnt, gibt es unterschiedlich gute Sortierverfahren. Fangen wir zunächst mit den langsameren an. Jene sind nicht nur leicht zu verstehen, sondern auch leicht zu implementieren. Sobald Sie aber mehr als 1000 Elemente Sortieren müssen, rate ich dringend von jenen ab. Unter 1000 Elementen nehmen sich die einzelnen Verfahren nichts (liegt bei den heutigen Rechnern im Millisekundenbereich).

Die folgenden Algorithmen haben die durchschnittliche Laufzeit n2, wobei das n für die Anzahl der Elemente steht. Die benötigte Zeit für die Sortierung, wächst also quadratisch mit der Anzahl der Elemente.

Zum Seitenanfang
Zum Inhaltsverzeichnis

37.1.2 Selectionsort

37.1.2 Selectionsort

Bei diesem Verfahren wir jetzt z.B. der sortierte Bereich von vorne aufgebaut, wobei er immer mit dem nächst gößeren Element erweitert wird. Dieses nächst größere Element wird durch gezielte Auswahl ermittelt, also selektiert und mit dem ersten noch nicht sortierten Element getauscht.

Dieses Verfahren arbeitet vom Ersten bis zum vorletzten Element. Das letzte braucht logischerweise nicht mehr betrachtet werden, weil es kein kleineres Element mehr geben kann. Schauen wir uns dies wieder an der Grafik an.

Veranschaulichung des Selectionsort Sortierverfahrens

Als erstes wird also das erste Element, nämlich die 6, betrachtet und es wird in der Restliste nach einem Element gesucht, welches zum einen kleiner als die 6 ist und zum anderen noch das kleinste Element überhaupt ist. Die Suche ergibt 1 und so werden die zwei Elemente getauscht.

Im nächsten Schritt wird wieder die 6 betrachtet, weil sie wieder das erste Element im unsortierten Bereich ist. Die Suche findet jetzt die 2 als kleinstes Element und die zwei Elemente werden wieder getauscht.

Auch hier sollte der Rest wieder klar sein und für die Suche gilt wieder genau das gleiche wie für Bubblesort. Auch hier müssen Sie darauf achten, dass Sie nicht unnötig gleiche Elemente tauschen, um eine Vorsortierung nicht zu zerstören.

Zum Seitenanfang
Zum Inhaltsverzeichnis

37.1.3 Insertionsort

37.1.3 Insertionsort

Bisher waren die Algorithmen immer so konzipiert, dass in jedem Schritten, immer die komplette Liste durchlaufen werden musste und oftmals dann sogar nichts mehr gemacht wurde (außer die vermeintlich unnötigen Vergleiche). Gerade dann, wenn schon eine sortierte Liste vorliegt, brauchen diese Algorithmen trotzdem immer ihre quadratische Laufzeit, obwohl sie effektiv nichts machen. Abhilfe schafft hier Insertionsort, was im optimalen Fall, nämlich der bereits sortierten Liste, nur einmal komplett durchläuft und feststellt, dass die Liste sortiert ist. Somit hat dieses Verfahren im besten Fall lineare Laufzeit. Nur im schlimmsten Fall (umgekehrt sortierte Liste) benötigt das Verfahren auch quadratische Laufzeit. Aber wie funktioniert dieses Verfahren jetzt?

Insertionsort fängt immer an der zweiten Position an, wobei angenommen wird, das alles was davor ist, sortiert ist. Nun wird das aktuell betrachtete Element immer in diesen sortierten Bereich gezielt eingefügt. Im Fall einer Liste geschieht dies durch das umhängen von Pointern. Im Falle eines Arrays muss das Element so lange nach vorne getauscht werden, bis es an der richtigen Stelle steht. Um diese richtige Stelle zu finden, muss man jetzt aber nicht immer bis ganz nach vorne laufen. Da alles davor schon sortiert ist, muss man nur dann noch weiter nach vorne laufen, wenn das Element vor dem aktuell betrachteten, größer ist als das aktuelle. Im Fall einer Vorsortierten Liste, wird dies also nie auftreten und das erklärt die lineare Laufzeit. Schauen Sie sich auch hier wieder das entsprechende Beispiel an.

Veranschaulichung des Insertionsort Sortierverfahrens

Zuerst wird die 1 betrachtet und so lange nach vorne gelaufen, bis ein Element gefunden wird, welches nicht mehr größer ist. Die 6 ist größer und da vor ihr kein Element mehr kommt, also auch kein Element mehr größer ist, wird die 1 vorne eingefügt.

Im zweiten Schritt wird jetzt die 7 betrachtet und es wird festgestellt, dass das davor stehende Element kleiner ist, woraus zu schlussfolgern ist, dass davor nur noch kleinere Elemente kommen und die 7 somit schon an der richtigen Stelle steht.

Jetzt wird die 2 betrachtet und wieder fast bis ganz vorne verschoben, wobei alle Elemente dazwischen nach rutschen. Die 5 kommt dann anschließend zwischen 2 und 6 und so geht das Spiel weiter bis zum Ende.

Wie Sie sehr schön sehen können, braucht man im Durchschnitt sogar nur noch ein wenig mehr als die Hälfte des sortierten Bereiches zu durchlaufen und somit auch nur noch die Hälfte an Vergleichen. Somit ist Insertionsort in dieser Kategorie der klare Sieger.

Zum Seitenanfang
Zum Inhaltsverzeichnis

37.1.1 Bubblesort

37.1.1 Bubblesort

Bei diesem Verfahren baut man z.B. den Sortierten Bereich hinten auf, indem man von vorne her immer das größere Element noch hinten blubbern lässt. Anschließend wird das Selbe wieder von vorne gemacht, nur dass man jetzt nur noch zum vorletzten Element läuft, da das Letzte ja jetzt schon an der richtigen Stelle steht. Dies wird so lange gemacht, bis man nur noch ein Element hat. Schauen wir uns dies an nachstehender Grafik an.

Veranschaulichung des Bubblesort Sortierverfahrens

Damit das Prinzip der Blasen besser deutlich wird, habe ich die Liste nicht von links nach rechts, sondern von unten nach oben aufgebaut. Im Ersten Durchlauf wird die 6 mit der 1 verglichen und da die 6 größer ist, werden die Elemente vertauscht, also die 6 blubbert einen Schritt nach oben. Anschließend wird die 6 mit der 7 verglichen und es wird festgestellt, dass nichts getan werden muss, die 6 also nicht weiter hoch blubbert. Nun wird die 7 mit der 2 verglichen und da die 7 größer ist, blubbert sie hoch, was zur Folge hat, dass sie nun noch mit der 5 verglichen wird, wobei sie noch weiter hoch blubbert. Am Ende des ersten Durchlaufes ist die 7 bis ganz nach oben geblubbert und verlässt die "Meeresoberfläche", also den unsortierten Bereich.

Im zweiten Durchlauf setzt jetzt die globale Erderwärmung ein, welche das Meer soweit verdampfen lässt, dass sie unterhalb der 7 ist und der Spaß geht von vorne los. Zuerst wird wieder die 1 mit der 6 verglichen und es muss nichts getan werden. Dann wird die 6 mit der 2 verglichen und blubbert eins hoch, wo sie dann mit der 5, dann mit der 3 und abschließend mit der 4 verglichen wird und somit ganz hoch blubbert.

Der Rest sollte jetzt klar sein, aber eines sollte noch erwähnt werden. Falls man diesen Algorithmus implementiert, sollte man die vergleiche immer mit dem kleiner oder größer Operator realisieren. Wenn man z.B. kleiner gleich benutzt, kann es vorkommen, dass z.B. 2 "gleiche" Elemente getauscht werden. Nun werden Sie sich fragen, was daran so schlimm sein soll? Nun, stellen wir uns eine Datenbank vor mit einer Adresstabelle. Angenommen wir haben zuerst die Ansicht nach dem Alter sortiert und wollen jetzt die Liste nach den Vornamen sortieren. Normalerweise erwarten wir, dass jetzt Hans Müller und Hans Meier noch nach ihrem alter sortiert sind. Vertauschen wir also den einen Hans mit dem anderen Hans, dann zerstören wir die Vorsortierung. Man nennt Sortieralgorithmen die so etwas machen, instabile.

Zum Seitenanfang
Zum Inhaltsverzeichnis

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