Eine äusserst wichtige Aufgabe von Computern ist es, Daten zu sortieren. Es ist nicht verwunderlich, dass es dementsprechend viele Sortier-Algorithmen gibt, wovon einige wenig brauchbar, kompliziert, zu langsam, oder aber eben sehr schnell, einfach, universal sind. Hier werden die bekanntesten kurz vorgestellt.
Zuvor einige Bemerkungen: Es handelt sich hierbei stets um Array-Sortier-Algorithmen, das bedeutet, dass die Elemente linear hintereinandergeordnet sind und jedes Element durch einen Index eindeutig bestimmt ist und direkt dereferenziert werden kann. Im folgenden wird zur Vereinfachung (oBdA: ohne Beschränkung der Allgemeinheit) stets angenommen, dass das Array mit einfachen Zahlenwerten gefüllt ist. Ausserdem wird immer vom Kleinsten zum Grössten sortiert.
Es werden hier nur Sortieralgorithmen angeschaut, die vollständig intern ablaufen können, was bedeutet, dass der Speicherplatz für den ganzen Ablauf ausreicht und nicht auf Zwischenspeichermedien wie Harddisk zurückgegriffen werden muss.
Des weiteren wird ein Pseudo-Programmcode für alle Sortierverfahren aufgelistet werden. Das Array heisst stets A und hat stets die Länge n (Vorsicht, das Array geht aber von Index 0 bis n-1). Den Inhalt der Speicherstelle 0 wird beispielsweise durch A[0] dereferenziert. Zum besseren Verständnis wird im eigentlichen Pseudocode auf Optimierungen verzichtet, sie sind jedoch im Nachhinein beschrieben. Auf Initialisierungen wird ebenfalls verzichtet. Falls also einmal eine unbekannte Variable x auftauchen sollte, so ist die einfach vom Typ Element.
Für die Analyse muss beachtet werden, dass die für die Qualität ausschlaggebenden Werte die Anzahl Vertauschungen und Anzahl Vergleiche sind. Dabei nimmt man meistens an, dass ein Vergleich um einiges weniger aufwändig ist, als eine Vertauschung. Es wird zudem unterschieden zwischen best- average- und worst-case (Bestenfalls, im Mittel, Schlechtestenfalls). Ein weiterer Faktor ist die Fähigkeit, vorsortierte Arrays möglichst gut auszunutzen. Alle anderen Vor- und Nachteile dieser Algorithmen entnehme man bitte anderen Quellen.
Sortieren durch Auswahl, Selection Sort
Dieser Algorithmus ist einer der einfachsten. Man geht einfach stets den unsortierten Teil des Arrays von links nach rechts durch und merkt sich den Index des Minimums. Wenn man dieses gefunden hat (das heisst, wenn man am rechten Rand angekommen ist und sich somit sicher ist, dass kein anderes Element das Minimum sein kann), dann vertauscht man einfach dieses Minimum mit dem Element, das sich an linkester Stelle des unsortierten Teiles befindet. Nun gehört dieses Minimum-Element zu dem sortierten Teil des Arrays und man beginnt wieder von vorne.
Programmcode:
//sortiere jede Stelle des Arrays Schleife: für s=0 bis s=n-1 //min beinhaltet stets den Index des möglichen Minimums Setze min=s //suche das Minimum Schleife: für p=s bis p=n-1 Falls A[p] kleiner A[min] dann setze min=p Schleifenende. //Vertausche das gefundene Minimum x=A[s]; A[s]=A[p]; A[p]=x; Schleifenende.
Optimierungen
Äussere Schleife: Es muss nur bis n-2 gegangen werden, da das letzte Element garantiert das Minimum des restlichen Teil-Arrays (welches nur aus diesem Element besteht) ist.
Innere Schleife: Da min vor der Schleife definiert wurde als min=s, muss dieses s nicht nochmal überprüft werden. man kann mit s+1 beginnen.
Vertauschung: Man könnte noch überprüfen, ob min==s, denn wenn ja, muss keine Vertauschung vorgenommen werden, da das Element mit sich selbst vertauscht werden müsste.
Analyse
worst: Array ist aufsteigend sortiert, das allergrösste Element steht jedoch bei Index 0
best: Array ist bereits sortiert
Vertauschungen:
nicht optimiert: worst:n, best:n
optimiert: worst:n-1, best:0
Vergleiche:
Stets O(n^2)
Vorsortiertheit: Kein verallgemeinerbarer Einfluss
Mittlere Laufzeit: O(n^2)
Sortieren durch Einfügen, Insertion Sort
Hier geht man ebenfalls von links nach rechts durch das Array durch. Nur wird hier angenommen dass der Teil links des aktuellen Index stets vorsortiert ist. Ein neues Element kann in diese vorsortierte Menge eingefügt werden, indem man das Element des aktuellen Index solange mit dem links davon stehenden vertauscht, bis dass es sich in diese vorsortierte Menge korrekt einordnet.
Programmcode:
//sortiere jede Stelle des Arrays Schleife: für s=0 bis s=n-1 //akt enthält den Index, an dem das einzuordnende Element liegt Setze akt=s Schleife: Solange (akt grösser 0) und (A[akt-1] grösser A[akt]) //Vertausche die beiden Nachbarn x=A[akt-1]; A[akt-1]=A[akt]; A[akt]=x; akt=akt-1 Schleifenende. Schleifenende.
Optimierungen
Vorsicht: Bei manchen Programmiersprachen muss das Abbruchkriterium der inneren Schleife in zwei separate Bedingungen unterteilt werden, da ansonsten, obschon akt==0 ist noch auf den Index akt-1 zugegriffen werden würde.
Äussere Schleife: Die Schleife kann bereits bei s=1 starten, da das erste Element automatisch eine vorsortierte Menge bildet. Grundsätzlich wird das einzusortierende Objekt ja nach links wandern. Es lonht sich also, sich das Objekt in einer separaten Variablen zu merken, die grösseren Nachbarn einfach eines nach rechts zu schieben, und das Element erst dort tatsächlich einzutragen, wo es korrekterweise hingehört.
Analyse
worst: Array ist invers sortiert (vom Grössten zum Kleinsten)
best: Array ist bereits sortiert
Vertauschungen: worst:O(n^2) best:0
Vergleiche:
nicht optimiert worst:O(n^2), best:n
optimiert worst:O(n^2), best:n-1
Vorsortiertheit: Weniger Vertauschungen, falls vorsortierte Teile eher links stehen.
Mittlere Laufzeit: O(n^2)
Shell Sort
Shellsort beruht auf der Überlegung, dass das Sortieren durch Einfügen soviel Zeit braucht, da beim nach-links-Transportieren stets nur ein einzelner Schritt getan werden kann. Shellsort wirkt dem entgegen, indem es zuerst grosse Sprünge durchführt, und dann mit der Zeit immer kleinere. Shellsort vergleicht also zuerst das erste mit dem letzten Element. Dann, im nächsten Durchgang das erste mit dem zweitletzten und das zweite mit dem letzten, usw.
Programmcode:
//gehe alle Abstände durch (abwärts) Schleife: für d=n-1 bis d=1 //gehe alle erreichbaren Elemente durch Schleife: für s=0 bis s=n-1-d falls A[s+d] kleiner A[s] dann //Vertausche die beiden x=A[s+d]; A[s+d]=A[s]; A[s]=x; Schleifenende. Schleifenende.
Optimierungen
Angeblich sei es möglich, die Abstände nicht jedesmal nur um 1 zu verringern. Genaues ist mir jedoch nicht bekannt.
Analyse
worst: Array besitzt Dreiecksform ( /\ oder \/ ): ähnliche Werte haben gleichen Abstand zur Array-Mitte
best: Array ist bereits sortiert
Vertauschungen: worst:O(n^2), best:0
Vergleiche: worst:O(n^2), best:O(n^2)
Vorsortiertheit: Keinerlei Vorteil (Vorsortiertheit wird vollständig zerstört)
Mittlere Laufzeit: O(n^2)
Sortieren mit Blöterli, Bubble-sort
Wohl der schlimmste Algorithmus überhaupt. Beim Bubblesort wird das Array stets von ganz links nach rechts bis vor den sortierten Teil durchwandert und das Maximum mitgeführt. Das bedeutet, dass für jedes Element überprüft werden muss, ob es grösser ist, als der rechte Nachbar, wenn ja, werden die beiden vertauscht, wenn nein, ist der rechte Nachbar das neue Maximum. Am rechten Rand angekommen gehört das Maximum nun zu dem sortierten Teil. Der Algorithmus heisst so, da das Maximum wie eine Luftblase aufsteigt (bzw hier nach rechts wandert).
Programmcode:
//sortiere jede Stelle des Arrays Schleife: für e=n-1 bis e=0 //max beinhaltet stets den Index, des aktuellen Maximums Setze max=0 Schleife: Solange max kleiner e falls A[max+1] kleiner A[max] //Vertausche die beiden Nachbarn x=A[max]; A[max]=A[max+1]; A[max+1]=x; max=max+1 Schleifenende. Schleifenende.
Optimierungen
Äussere Schleife: Die Schleife kann bereits bei e=1 stoppen, da das erste Element automatisch kleiner ist als alle anderen. Wiederum kann das Maximum in einer separaten Variablen gespeichert werden, bis dass es durch ein anderes Maximum abgelöst wird.
Analyse
worst: Array ist invers sortiert (vom Grössten zum Kleinsten)
best: Array ist bereits sortiert
Vertauschungen: worst:O(n^2), best:0
Vergleiche: worst:O(n^2), best:O(n^2)
Vorsortiertheit: Keinerlei Einfluss.
Mittlere Laufzeit: O(n^2)
Quick-Sort
Nach diesen sehr einfachen und normalerweise unbrauchbaren Sortieralgorithmen, kommt nun gleich der bekannteste Vertreter der nlogn-Algorithmen. Quicksort ist ein relativ leicht verständlicher (da intuitiv) aber doch schneller Algorithmus.
Intuitive Idee: Wenn man einen durcheinandergeratenen Stapel Blätter nach Seitenzahl (1 bis 100) sortieren will, so könnte man zuerst einmal einen Stapel machen, der alle Nummern von 1 bis 50 enthält (natürlich noch nicht sortiert) und einen zweiten mit den Nummern 51 bis 100. Sodann nimmt man sich jeden Stapel einzeln vor und macht aus denen wiederum jeweils zwei Stapel: 1 bis 25, 26 bis 50, 51 bis 75 und 76 bis 100. Wie es weitergeht, kann man sich nun erahnen: Wiederum nimmt man sich jeden einzelnen Stapel vor und teil ihn in zwei andere... Ganz zum Schluss hat man 100 einzelne Stapel (mit jeweils einem Blatt) und kann sie nur noch aufeinanderstapeln. Sortiert!
Dieses Verfahren des Aufteilens und danach des Zusammenfügens nennt sich Divide-and-Conquer (teile und herrsche). Daraus resultiert Typischerweise eine Laufzeit von O(n log2 n).
Dies ist fast genau die Idee des Quicksort-Algorithmus. Mit einem Unterschied: Normalerweise weiss man nicht, welches der mittlere Wert eines Stapels ist (In diesem Beispiel also die Zahl 50). Deswegen wählt man normalerweise einen zufälligen Wert aus und teilt den grossen Stapel folgendermassen auf zwei kleinere auf: Einen mit allen Zahlen kleiner als der gewählte Mittelwert und einer mit allen Zahlen grösser als der gewählte Mittelwert. Tatsächlich ist es bewiesen, dass dadruch die mittlere Laufzeit des Algorithmus nach wie vor O(n log2 n) ist.
Um dieses nlogn genau zu verstehen, möchte ich auf Fachliteratur verweisen. Was aber interessant ist, ist, dass kein Sortieralgorithmus schneller sein kann als nlogn. Der genaue Beweis ist etwas mühsam, hier aber die Grundidee:
Man stelle sich sämtliche Permutationen (mögliche Anordnungen) der Werte im Array vor: Es sind n! Stück. Sodann setzt man diese in einen Entscheidungsbaum (Binärbaum), sodass durch möglichst wenige Entscheidungen die korrekte Permutation gefunden werden kann. Der beste denkbare Sortieralgorithmus (der als einziges Werkzeug das Vergleichen von zwei Werten kennt) könnte diesen Baum in jedem Schritt um eine Stufe weiter nach unten kommen. Das bedeutet, dass er, um eine beliebige Permutation zu finden, höchstens log(n!) Schritte braucht (Er muss einfach die Höhe des Baumes überwinden). Und zu diesem log(n!) gibt es nun eine bewiesene Näherungsformel von einem gewissen Herrn HabkeineAhnungmehrwiederheisst, die besagt, dass (für n unendlich gross) die Gleichung O(log(n!))=O(n log(n)) gilt.
Doch genug der mathematischen Tatsachen. Ein paar Vorbemerkungen zum Programmcode: Der Quicksort-Algorithmus kann nur rekursiv gelöst werden. Das bedeutet, dass Quicksort aus einer Funktion besteht, die zu Beginn aufgerufen wird, sich jedoch dann selbständig wiederum aufruft. In diesem Zusammenhang ist es wichtig, zu verstehen, dass die Werte innerhalb einer Funktion bei einem Aufruf einer weiteren Funktion solange abgespeichert werden, bis dass die aufgerufene Funktion wieder zurückspringt. Wichtig ist dabei aber vor allem, dass die Werte nicht als Variablen-Parameter, sondern als Wert-Parameter übergeben werden dürfen, da ansonsten die Werte überschrieben werden.
Im folgenden Programm wird angenommen, dass das Array A global definiert ist, es also nicht zusätzlich noch zur Funktion übergeben werden muss. l und r stehen für den linken und rechten Rand des zu betrachtenden Array-Teiles. Aufgerufen Wird die Funktion mit l=0 und r=n-1. Das Mittel-Element m berechnet durch m=A[(l+r) DIV 2], wobei DIV die Ganzzahldivision ist.
Programmcode:
Funktion Quicksort(l,r); Neue Variablen: m, a, b //m ist der Vergleichswert Setze m = A[ (l+r) DIV 2 ] Setze a=l und b=r Schleife: Schleife: Solange A[a] kleiner als m, setze a=a+1; Schleifenende Schleife: Solange A[b] grösser als m, setze b=b-1; Schleifenende Falls nun a grössergleich b, dann beende die Schleife Ansonsten //vertausche die beiden Werte x=A[a];A[a]=A[b];A[b]=x setze a=a+1 und b=b-1 Schleifenende. Falls nun a=b dann a=a+1; b=b-1 Falls b grösser als l dann rufe Funktion auf: Quicksort(l,b) Falls a kleiner als r dann rufe Funktion auf: Quicksort(a,r) Funktionsende.
Um dieses Programm zu verstehen, gibts hier noch eine extra-Erklärung. m beinhaltet also den Wert, nach dem der Stapel Papier aufgeteilt wird (im folgenden wird auch manchmal m als der Index dieses Elements angesehen, was zwar nicht korrekt ist, aber die Erklärung etwas erleichtert). Alle Werte, die kleiner sind wie dieser Wert, gehören auf die linke Seite, alle, die grösser sind, auf die rechte. Das bedeutet, wir fangen beim linkesten Papier an (a=l) und schauen, ob es kleiner wie m ist. Wenn ja, dann ist es bereits auf der richtigen Seite und man überprüft das nächst rechtere Papier. Wenn nein, dann muss es mit einem Papier auf der rechten Seite ausgetauscht werden. Deshalb schaut man nun auf der rechten Seite, ob das Papier b (welches anfangs das Papier r war) auch tatsächlich auf die rechte Seite gehört. Ist dies so, so schaut man sich das nächst linkere Papier an, usw, bis man ebenfalls ein Papier gefunden hat, das nicht auf die rechte Seite gehört.
Allgemein gilt nun, dass auf der linken Seite ein Papier liegt, das nach rechts gehört und eines rechts liegt, das nach links gehört. Also vertauscht man die beiden Papiere, und schreitet mit den beiden Zeigern a und b jeweils um eines weiter nach rechts bzw nach links. Sodann geht das Spiel von vorne los. Es könnte aber auch sein, dass auf der rechten oder linken Seite kein Papier mehr falsch gelegen hat. Dies bedeutet, dass entweder der Zeiger a soweit nach rechts gewandert ist, dass er b überholt hat, oder dass der rechte Zeiger soweit nach links gewandert ist, dass er a überholt hat. In beiden Fällen ist a grössergleich b. Sodann weiss der Algorithmus, dass er die Mitte überschritten hat, und somit die beiden Teilstapel bereit liegen. Also verlässt er die Schleife.
Der Fall, dass a=b tritt auf, wenn beide Variablen a und b gleichzeitig auf das Mittelelement m treffen. Da dieses Element nicht sortiert werden muss (es befindet sich ja in der Mitte zwischen den beiden Stapeln) können es sowohl a als auch b getrost überspringen. Dadurch haben sie sich gegenseitig überholt und die Schleife wird ebenfalls verlassen. Wieso überprüft man nicht a kleinergleich m, dann träte dieser Fall gar nie auf? Richtig, allerdings kann es dann jedoch sein, dass a aus dem Array herausläuft. Man stelle sich die Situation eines Arrays vor, bei welchem sämtliche Einträge gleich sind. Somit ist auch m dieser Wert. Wenn nun a überprüft, ob es kleinergleich ist wie m, so wird es stets nach rechts laufen und irgendwann auch b überholen (welches noch ganz rechts steht) und somit das Array verlassen. Dies kann zu bösen Fehlern führen. Durch das kleiner anstelle des kleinergleich werden zwar alle Elemente, die gleich sind wie m in beide Stapel verteilt, jedoch sind sie in diesen dann das jeweils grösste bzw kleinste Element.
Was nun sicher ist, ist, dass a auf das linkeste Element des rechten Stapels und b auf das rechteste Element des linkes Stapels zeigt. Also sortiert man zuerst den linken Stapel, aber nur dann, wenn b grösser ist als l. Wären sie gleich, dann würde dies bedeuten, dass der Stapel aus genau einem Papier besteht, und das ist in diesem Fall das Abbruchkriterium. Nur wenn mehr als ein Papier auf einem Stapel liegt, so wird der Quicksortalgorithmus mit den Index-Grenzen l und b aufgerufen. Mit dem rechten Stapel verhält es sich genau gleich, nur wenn a kleiner ist als r, befinden sich mehr als ein Blatt auf dem rechten Stapel, worauf dann Quicksort mit a,r aufgerufen wird. Sobald all diese Dinge erledigt sind, springt die Funktion zurück.
Optimierungen
Der Algorithmus selbst kann kaum optimiert werden. Der Knackpunkt von Quicksort ist die Wahl von m. Dieser Wert sollte wenn möglich die beiden Teilstapel in genau zwei Hälften teilen. Da jedoch aus einem Array nur in O(n) Zeit ermittelt werden kann, welchen Wertumfang es besitzt, ergäbe diese Evaluation wiederum eine Laufzeit von O(n^2). Es sind verschiedene Möglichkeiten möglich, m zu wählen:
m=l oder m=r: nur sinnvoll in zufälligen Arrays, Vorsortiertheit wird nicht ausgenutzt.
m=(l+r)/2: sinnvoll für vorsortierte Arrays, irrelevant in zufälligen Arrays.
m=zufallsindex: nur sinnvoll in zufälligen Arrays
m=3-Median: erstaunlich gute Schätzung: man nehme 3 Werte (Beispielsweise links, mitte und rechts) und nehme den mittleren davon.
Analyse
worst: Array beinhaltet lauter gleiche Werte oder m liegt anderweitig ungünstig
best: m liegt stets genau mittig
Vertauschungen: worst:O(n^2), average:O(n log n), best:0
Vergleiche: worst:O(n^2), average:O(n log n), best:O(n log n)
Rekursionen: worst:n, average:log n, best:log n
Vorsortiertheit: Je nach Wahl von m. Vorsortiertheit wird grundsätzlich zerstört.
Mittlere Laufzeit: O(n log n)
Merge Sort
Man sieht also, dass es durchaus Sortieralgorithmen gibt, die schneller sind, also andere. Trotzdem ist Quicksort nur im average-Case tatsächlich schneller. Ein Sortierverfahren, welches in jedem Fall nur nlogn Zeit braucht, ist Mergesort.
Zwar braucht Mergesort stets nur nlogn Zeit, dafür aber zusätzlichen Speicherplatz. Dazu dann später mehr. Beim Mergesort geht man wie bei Quicksort nach dem Divide-and-conquer-Prinzip vor. Man unterscheidet zwischen drei bekannten Verfahren: Mergesort, reines Mergesort und natürliches Mergesort
Mergesort:
Das grundlegende Verfahren von Mergesort ist das folgende: Man teilt das Array in zwei genau gleich grossen Teile (plus minus 1) und verfahre mit den beiden Hälften genau gleich. Sobald die Aufteilung beendet ist, werden die beiden Hälften (die durch die rekursive Aufrufung jetzt sortiert sind) zusammengefügt (Merge, dazu später mehr).
Hier noch eine etwas illustrativere Beschreibung: Man nehme den Stapel mit 100 Papieren und teile ihn auf in zwei Stapel mit je 50 Papieren. Sogleich nimmt man sich den einen Stapel vor und teilt ihn wiederum in zwei Stapel à 25 Papieren. Dies wird immer weiter gemacht, bis man irgendwann mal nur noch zwei Stapel mit je einem Papier vor sich liegen hat. Da diese nun nicht mehr weiter aufgeteilt werden können, beginnt man, sie zu zusammenzufügen (Ein Stapel mit nur einem Blatt ist sortiert). Sodann hat man einen Stapel mit 2 Blättern, die nun sortiert sind. Dieser Stapel kann nun gleichfalls mit dem (nach dem gleichen Prinzip sortierten) Nachbarstapel zusammengefügt werden, woraus dann ein sortierter Stapel mit 4 Blättern resultiert. Irgendwann liegen dann die beiden Anfangsstapel mit je 50 Blatt sortiert vor und können zusammengefügt werden. Danach erhält man das vollständig sortierte Array.
reines Mergesort:
Beim reinen Mergesort überspringt man die rekursive Aufteilung des Arrays in Hälften und geht stattdessen folgendermassen vor: Zuallererst nimmt man im gesamten Array nur alle Zweiergruppen 1-2, 3-4, 5-6, usw und merged sie zusammen. Dann nimmt man alle 4er-Gruppen 1-4, 5-7, 8-11, usw und merged diese zusammen. Dann alle 8er-Gruppen, usw, bis das Array sortiert ist.
Der Vorteil dieses Verfahrens ist, dass es iterativ gelöst werden kann, und das bringt einen enormen Geschwindigkeitsvorteil.
natürliches Mergesort:
Das natürliche Mergesort ist eine Art Erweiterung des reinen Mergesorts. Während man beim reinen Mergesort stets vom kleinstmöglichen zu sortierenden Arraystück ausgeht, überprüft man beim natürlichen Mergesort zuerst, ob es nicht bereits vorsortierte Teilstücke gibt, die dann sogleich als Ganzes genommen werden können.
Das Mergen
Der Programmteil, der dem Algorithmus den Namen gibt, wird hier noch etwas genauer beschrieben. Es ist genau dieser Teil, welcher auch verursacht, dass man O(n) zusätzlichen Speicher benötigt. Man gehe davon aus, dass man zwei Teil-Arrays A und B hat, die sortiert sind. Diese beiden Arrays liegen zwar bisher im Speicher, den das gesamte Array benötigen würde, aber beim Zusammenfügen reicht dieser Platz nicht mehr.
Wie man zwei Teile zusammenfügt, ist eigentlich ziemlich einfach: Man vergleicht die beiden Elemente, die zuvorderst der Teilstücke liegen und nimmt das kleinere davon und setzt es in ein neues grosses Stück.
Beispielsweise hat man die beiden sortierten Arrays [1,3] und [2,4]. Man weiss also, dass das schlssendliche Array 4 Elemente speichern muss: [?,?,?,?]. Nun überprüft man die beiden ersten Elemente 1 und 2. Da 1 kleiner ist als 2, fügt man die 1 in das neue Array ein: [1,?,?,?]. die ursprünglichen Arrays sehen nun so aus: [3] und [2, 4]. Wieder überprüft man die ersten beiden Elemente und nimmt somit die 2 aus der zweiten Menge heraus. Dadurch entsteht die Gesamtmenge [1,2,?,?]. Übrig bleiben noch die Arrays [3] und [4].
Dies geht solange weiter, bis dass ein Teilarray komplett leer ist: Im nächsten Schritt nimmt man die 3 in das grosse Array: [1,2,3,?]. Nun ist das erste Array leer und das zweite kann nun komplett übernommen werden: [1,2,3,4].
Man kann sich schnell denken, dass für das Mergen die Teilarrays nicht zwingendermassen gleich gross sein müssen (wie es auch beim natürlichen Mergesort gebraucht wird). Aber man sieht auch, dass, wie gesagt, zustätzlicher Platz nötig ist. Man möge es doch ausprobieren, ob es nicht anders ginge (angeblich gibt es eine Lösung, die muss allerdings so wahnsinnig kompliziert sein, dass es sich geschwindigkeitsmässig gar nicht mehr lohnt, sie auszuprogrammieren).
Der folgende Programmcode ist nur für das Mergen zuständig. Dieses wird für alle drei Verfahren verwendet. Das Array A sei wieder global definiert. Der Algorithmus hier erstellt zuerst von den beiden Teilarrays je eine Kopie und schreibt sie dann direkt zurück ins Array A. Die übergebenen Werte a, m, e beschreiben den Anfangs- und End-Index des ersten und den End-Index des zweiten Arrays (T1 geht von a bis m, T2 geht von m+1 bis e). Man beachte, dass der Index a gleichzeitig auch der Index ist, an den das gemergete Array geschrieben wird.
Programmcode:
Funktion Merge(a, m, e); Neues Teil-Array: T1 mit Grösse m-a+1 Neues Teil-Array: T2 mit Grösse e-m //Index der beiden Teilarrays und des Hauptarrays Neue Variablen: p1, p2, p p1=0, p2=0, p=a Schleife: //Das vorderste Element von T1 ist das kleinste Falls T1[p1] kleiner T2[p2], dann A[p]=T1[p1] p=p+1 p1=p1+1 //Das vorderste Element von T2 ist das kleinste Ansonsten A[p]=T2[p2] p=p+1 p2=p2+1 //Falls erstes TeilArray aufgebraucht Falls nun p1 gleich m-a+1 //Kopiere restliche Elemente von T2 Schleife: Für i=p2 bis e-m-1 A[p]=T2[i] p=p+1 Schleifenende. Gehe zu EndeDerFunktion //Falls zweites TeilArray aufgebraucht Falls nun p2 gleich e-m //Kopiere restliche Elemente von T1 Schleife: Für i=p1 bis m-a A[p]=T1[i] p=p+1 Schleifenende. Gehe zu EndeDerFunktion Schleifenende. EndeDerFunktion: Lösche Teilarrays T1 und T2 wieder Funktionsende.
Wenn man diese Funktion erst einmal hat, ist der Rest nicht mehr schwierig. Folgendes ist der Code für das allgemeine, rekursive Mergesort, wobei l und r die beiden Randpunkte des jeweiligen Arrays sind:
Funktion Mergesort(l,r) //Das Array besteht nur aus einem Element Falls l=r Funktionsende. //setze die Mitte m = (r+l) DIV 2 //Sortiere das linke Teilarray Mergesort(l,m) //Sortiere das rechte Teilarray Mergesort(m+1,r) //Füge die beiden Teilarrays zusammen Merge(l,m,r) Funktionsende.
Diese kleine Funktion generiert zusammen mit der oben aufgeführten Merge-Funktion ein sortiertes Array.
Das folgende Programm ist die iterative Lösung für das reine Mergesort: Wieder wird angenommen, dass A global definiert ist, und dass zudem die Grösse des Arrays als GrösseA bekannt ist.
Funktion ReinMergesort() //Setze s (Step) auf Einerschritte s=1 Schleife: Solange x kleiner als GrösseA //Setze imaginären vorherigen rechten Rand r=-1 Schleife: Solange r+s kleiner als GrösseA-1 //linker Rand ist vorheriger rechter Rand + 1 l=r+1 //Setze Mitte so, dass linkes Teilarray s Elemente enthält m=l+s-1 Falls m+s kleiner GrösseA //Setze rechten Rand so, dass zweites Teilarray ebenfals s Elemente enthält r=m+s Ansonsten //Sonst setze rechten Rand auf das letzte Arrayelement r=GrösseA-1 Merge(l,m,r) Schleifenende. //Verdopple die Schrittweite s=s*2 Schleifenende. Funktionsende.
Für das natürliche Mergesort gibt es verschiedene Implementationsmöglichkeiten. Hier wird eine Art Bastelarbeit vorgestellt, die zwar funktioniert, jedoch nicht gerade schöner Programmierstil ist. Sie wird deshalb auch nicht allzu stark behandelt:
Zuerst definiert man eine weitere Funktion, die als Parameter den Startindex für die Suche nach aufsteigenden Array-Elementen erhält. Diese Funktion sucht nun ab diesem Index nach dem letzen Element, das noch eine aufsteigende Reihe bildet und gibt dessen Index zurück. Beispielsweise wäre dies im Array [1,5,9,3,6,2] der Index 2, da das Teilarray [1,5,9] die linkeste aufsteigende Reihe ist.
Für die nachfolgende Implementierung wird zusätzlich angenommen, dass dieses Suchen nach der aufsteigenden Reihe automatisch das letzte Element des Arrays zurückgibt, falls über das Array hinaus gelesen werden sollte.
Man implementiere nun eine inverse Rekursion. Dies bedeutet, dass man zu Beginn annimmt, dass man sich auf der höchsten Rekursionsstufe befindet. Sodann sucht man sich zwei aufsteigende Teil-Arrays und merged diese. Wenn nun noch nicht das ganze Array durchlaufen ist, so setzt man die Rekursionstiefe eines nach oben und ruft dieselbe Funktion mit der ursprünglichen Rekursionstiefe für den nächsten Index auf. Wenn diese Funktion dann geendet hat, kann man das nächste Array mit dem ersteren mergen, überprüft jedoch wiederum, ob das Array bereits fertig ist. Dies geht solange weiter, bis dass das Array vollständig sortiert ist. Somit muss zusätzlich noch definiert werden, dass wenn die Funktion nicht mit der höchsten Rekursionstiefe aufgerufen wird, diese die Rekursion bis auf die tiefste Stufe weiterleitet. Ausserdem muss stets die höchste Rekursionsstufe mitgegeben werden.
Im folgenden Programm ist d die aktuelle Rekursionsstufe und h die höchste. Die Funktion wird aufgerufen mit ReinMergesort(0,0,0).
Funktion ReinMergesort(l,d,h) //Falls auf der tiefsten Rekurstionsstufe Falls d=0 //Suche die beiden m=SucheAufsteigend(l) //aufsteigenden Reihen r=SucheAufsteigend(m+1) //Falls auf irgendeiner anderen Rekurstionsstufe Ansonsten //Rufe rekursiv auf für linkes Teilarray m=ReinMergesort(l,d-1,h) //Rufe rekursiv auf für rechtes Teilarray r=ReinMergesort(m+1,d-1,h) //Füge die beiden Teile zusammen Merge(l,m,r) //Falls Funktion der höchsten Rekurstionsstufe Falls d=h Schleife: Solange r kleiner als GrösseA-1 //Erhöhe Rekursionsbasis h=h+1 //Setze Mitte auf vorherigen rechten Rand m=r //Rufe rekursiv das restliche rechte Array auf r=ReinMergesort(m+1,h-1,h) //Füge das erhaltene Teil-Array mit dem linken zusammen Merge(l,m,r) Schleifenende Gib r zurück. Funktionsende.