| Effizientes Programmieren |

Effizientes Programmieren - Teil 6

Als Abschluß dieses Kurses beschäftigen wir uns noch mit den verschiedensten Sortiermethoden. Dabei werden wir die wichtigsten Verfahren behandeln und uns auch Gedanken über ihr Laufzeitverhalten machen.

Es gibt wohl ein Thema, das bei keiner Abhandlung über effiziente Algorithmen fehlen darf: die Sortierverfahren. Gerade auf diesem Gebiet wurden langjährige Forschungen betrieben und in keinem anderen Bereich sind die Geschwindigkeitsvorteile eines guten Algorithmusses gegenüber einem schlechten so deutlich geworden wie bei den Sortierverfahren. Prinzpiell gibt es eine wahre Unzahl an verschiedenen Methoden, Schlüsseln aus einer unsortierten Liste a[N] in sortierter Form anzureihen, einige davon sind jedoch entweder zu uneffizient oder allzu exotisch um in diesem Kurs berücksichtigt werden zu können. Trotzdem wollen wir mit den elementaren Sortierverfahren beginnen und uns anschließend mit etwas diffizileren beschäftigen.

Unser erster Algorithmus nennt sich Sortieren durch Auswahl und geht nach der folgenden, recht einfachen Methode vor: es werden alle Elemente der Reihe nach durchgegangen und in einer Variablen vermerkt, wo das kleinste zu finden ist. Nach dem Durchlauf wird dieses Element mit dem ersten vertauscht (mit a[0]). Somit befindet sich das kleinste Element schon einmal am Anfang der zu sortierende Liste. Nun suchen wir im der restlichen Feld a[1]..a[N-1] wieder den kleinsten Eintrag und vertauschen ihn mit dem Feld a[1]. Auf diese Weise fahren wir N-1 mal fort, denn dann sind alle Elemente in die richtige Reihenfolge gebracht und unsere Aufgabe beendet. Das Programm zu "Sortieren durch Auswahl" finden Sie in Listing 1. Leider ist dieser Suchvorgang nicht besonders schnell, da das Verfahren zwei inneinander geschachtelte Schleifen besitzt - das kostet natürlich Zeit. Einen anderen Weg geht "Bubblesort". Hier wird die Liste durchlaufen und dabei jedes Feld a[i] mit seinem Nachfolger a[i+1] verglichen. Ist dabei a[i]>a[i+1] werden die beiden Elemente vertauscht. Dadurch wandert das größte Element der Liste mit dem ersten Durchlauf an das Ende des Feldes. Der letzte Feldeintrag a[N-1] muß also im weiteren nicht mehr betrachtet werden. Die übrigen Elemente a[0]..a[N-2] müssen allerdings noch nicht sortiert sein, da sich ihre Positionen jeweils maximal um eins nach links bewegt haben können. Deshalb werden diese wiederum auf dieselbe Weise durchlaufen. Dies wird dann sooft wiederholt, bis keine Vertauschungen von Nachbarelementen mehr nötig waren, denn dann ist die Liste sicher sortiert. Bubblesort können Sie in Listing 2 finden. Auch hier kommen zwei geschachtelte Schleifen vor, die äußere wird jedoch im allgemeinen früher terminieren als jene beim Sortieren durch Auswahl, weshalb das Bubblesort auch meist schneller geht. Es gibt jedoch auch Fälle, wo auch Sortieren durch Auswahl seine Berechtigung hat, nämlich dann, wenn viele Datenmengen beim Vertauschen von Elementen bewegt werden müssen. Beim Sortieren durch Auswahl werden nämlich immer maximal N Vertauschungen durchgeführt, während beim Bubblesort unter Umständen viele Elemente lange herumgeschoben werden, bis sie am richtigen Platz gelandet sind.

Bubblesort ist trotzdem ein sehr populäres Verfahren, obwohl es in seinem Laufzeitverhalten nur als ziemlich schlecht bezeichnet werden kann. Allerdings ist es leicht zu implementieren und kann in speziellen Fällen sogar sehr schnell sein, nämlich genau dann, wenn die Liste schon recht gut sortiert ist und durch ein paar Vertauschungen schnell fertigsortiert werden kann. Seinen Namen hat Bubblesort übrigens dadurch erhalten, daß die größten Elemente immer wie Luftblasen im Wasser an das Ende der Liste "aufsteigen".

Sortieren durch Suchen und Bubblesort sind - wie gesagt - recht einfache, elementare Suchverfahren. Wenn Sie schnell mal ein Suchverfahren brauchen und die Geschwindigkeit keine allzugroße Rolle spielt, haben diese Verfahren durchaus ihre Daseinsberechtigung. Für "kritischere" Aufgaben mit größeren Datenmengen sollte aber eher einer der folgenden Algorithmen Anwendung finden.

Das - für unseren Kenntnisstand - am einfachsten zu verstehende Sortierverfahren ist Heapsort. Sie erinnern sich sicherlich noch an die Datenstruktur Heap (Halde) aus dem dritten Teil unseres Kurses. Gleichgültig welches Element man zuletzt auf den Heap gelegt hat, man bekommt bei einer Leseoperation immer das kleinste zurückgeliefert. Wenn wir die Daten also als Heap vorliegen haben, können wir sie recht einfach sortieren. Wir holen uns das erste Element vom Heap und legen es an die Position a[0], das zweite kommt nach a[1] usw. Am Ende ist a[0]..a[N-1] fertig sortiert. Dieses Verfahren arbeitet sehr effizient. Wenn man die Daten also in einem Heap gespeichert hat, bietet sich die Verwendung von Heapsort geradezu an. Leider ist das nicht immer möglich, weshalb wir nun zu den beiden letzten (und leistungsfähigsten) Algorithmen kommen: Quicksort und Mergesort.

Beide haben zwei Dinge gemeinsam: sie folgen derselben Strategie und erfordern zum vollständigen Verständnis einiges an Abstraktionsvermögen. Letzteres liegt in ihrem rekursiven Aufbau begründet. Grundsätzlich müssen Sie sich folgendes immer vor Augen halten: die Algorithmen funktionieren! Das klingt auf den ersten Blick banal, wenn sie das nicht tun würden, wären sie eine genauere Betrachtung wohl kaum wert. Trotzdem ist diese Erkenntnis wichtig. Sie läßt nämlich den Schluß zu, daß, wenn sich der Algorithmus selbst aufruft (mit einer Teilfolge der gesamten Liste als Argument), die angegebene Folge von Elementen sortiert ist. Für den Anfänger, der mit Rekursionen nicht sehr vertraut ist, stellt das oft ein großes Problem dar. Der Algorithmus verwendet sich nämlich selbst mit dem erwarteten Ergebnis noch bevor er vollständig ausformuliert wurde. Wenn man jedoch bei jedem rekursiven Aufruf davon ausgeht, daß der Algorithmus das erwartete Ergebnis liefert, ist eine weitere Verfolgung der Routine nicht weiter schwierig. Sie sollten sich diese Betrachtungsweise auch angewöhnen, wenn Sie eigene rekursive Algorithmen entwickeln. Nehmen Sie bei jedem rekursiven Aufruf an, ihr Algorithmus tut mit dem angegebenen Teil genau das, was Sie von ihm erwarten, und das obwohl Sie ihn noch nicht fertig haben. Das hilft Ihnen, den bei rekursiven Programmen immer schwer zu durchschauenden Programmfluß besser zu überblicken. Kommen wir jetzt aber zurück zum Thema. Quicksort ist wohl das bekannteste Sortierverfahren. Es wurde 1962 von C.A.R. Hoare veröffentlicht und hat seinen Namen nicht zu unrecht. Es folgt der sogenannten Divide-and-Conquer-Strategie, einer überhaupt sehr populären und vielfältig einsetzbaren Idee. Divide-and-Conquer ist eine englische Übersetzung des lateinischen Originals "divide et impera". Dieser Begriff wurde schon von C. Julius Caesar geprägt, der die Divide-and- Conquer Strategie im Krieg gegen die Gallier einsetzte ("de bello gallico"). Er nützte die Teilung Galliens in verschiedene Stämme aus. Diese waren sich dann untereinander so uneinig, daß sie sich zu keiner Gesamtmacht gegen die römischen Truppen zusammenschließen konnten. Caesar hatte es also nicht mit einem recht großen Problem, sondern nur mit mehreren lösbaren Teilproblemen zu tun.

Auch in der Informatik verfolgt man gerne denselben Gedanken. Ein berühmtes Beispiel ist die fortschreitende Modularisierung von Programmen. Man teilt das Problem in mehrere Teilprobleme auf, diese werden dann von unterschiedlichen Moduln gelöst. Diese Module einzeln sind recht einfach zu entwickeln, das gesamte Programm aber in einem Stück geradezu unmöglich. Sie sehen also, die Grundregeln moderner Programmiertechniken gehen sogar schon bis zur alten Römerzeit zurück.

Gehen wir nun aber genauer auf die Arbeitsweise von Quicksort ein. Wenn die lineare Liste nur ein oder gar kein Element enthält, wird gleich abgebrochen, denn in diesen Fällen gibt es nichts zu sortieren. Andernfalls wird zuerst ein beliebiges Element k, das sogenannte Pivotelement, aus der Folge a[0]..a[N-1] ausgewählt. Dann wird die Liste in zwei Teilfolgen F1 und F2 aufgeteilt, wobei F1 alle Elemente enthält, die kleiner als k sind, und F2 alle größeren. Danach wird der Quicksort-Algorithmus auf jede der beiden Folgen ebenfalls angewandt. Dadurch werden diese vollständig sortiert (Quicksort funktioniert!). Anschließend werden die Folgen in der Reihenfolge F1, k, F2 zusammengehängt - fertig.

Problematisch ist jedoch die Implementierung der Aufteilung (Divide) in zwei Teilfolgen. Die meisten Quicksort-Implementationen gehen dabei aber einen trickreichen Weg. Anstatt aus der ursprünglichen Folge a[0]..a[N-1] durch umständliche Kopieroperationen zwei weitere zu machen wird die Folge a selber in zwei Teile geteilt. Man benützt dazu üblicherweise zwei Indices - einen auf den Anfang der ursprünglichen Folge (l für links) und einen auf das Ende (r). Für den ersten Aufruf von Quicksort sind diese 0 bzw. N-1. Dann wird l solange hinaufgezählt, bis a[l]>k. Somit wissen wir, daß alle a's bis exklusive a[l] teil von F1 sind. a[l] selber gehört aber nach F2, da es größer als k ist. Danach wird r solange dekrementiert, bis a[r]<k ist. a[r+1] bis a[N-1] gehören also nach F2, a[r] selbst aber nach F1. Deshalb wird a[l] mit a[r] vertauscht und die beiden Elemente stehen wieder richtig. Dies wird solange praktiziert, bis l>r, dann ist die Aufteilung perfekt. In diesem Fall stehen alle Elemente von F1 links von l und alle Elemente von F2 rechts von l. An die Position l selbst wird nun noch k reingesetzt, das ja zwischen F1 und F2 liegen soll. Schlußendlich werden die beiden Folgen durch rekursive Aufrufe von Quicksort sortiert. Listing 3 stellt die eben beschriebene Version von Quicksort als fertiges C-Programm dar. Wie Sie sicher wissen, gehört Quicksort in der Form der ANSI-C-Funktion qsort() zu den Standardfunktionen ihrer C-Bibliothek. Trotzdem kann es nicht schaden über die Funktionsweise dieses Sortieralgorithmusses Bescheid zu wissen. Als letztes der Sortierverfahren wollen wir uns noch mit Mergesort beschäftigen, das - wie Quicksort - der Divide-and-Conquer-Strategie folgt.

Mergesort - im Deutschen oft auch als Sortieren durch Verschmelzen bezeichnet - wurde 1945 von John von Neumann entwickelt. Es macht sich die Tatsache zunutze, daß das Verschmelzen von Folgen schneller geht als dessen Sortierung. Mergesort sortiert auf folgende geniale Weise: Die Ursprüngliche Liste a wird auch hier in zwei möglichst gleich große Teilfolgen F1 und F2 aufgeteilt. Als Teilungspunkt wird dabei genau das mittlere Element genommen. Beachten Sie aber, daß hier nicht wie bei Quicksort gilt, daß alle Elemente in F1 kleiner als k und alle Elemente in F2 größer als k sind. Die Teilfolgen enthalten einfach irgendwelche Schlüsseln. Danach wird der Mergesort-Algorithmus (er funktioniert!) auf beide Folgen angewandt. Wir gehen davon aus, daß diese danach sortiert sind. Nun nehmen wir die beiden Folgen und verschmelzen sie wieder zu einer einzigen, wobei wir die Sortierung beibehalten. Unser Problem reduziert sich beim Sortieren durch Verschmelzen, wie leicht zu erraten, auf das Verschmelzen von zwei sortierten Folgen F1 und F2 zu einer sortierten Folge F. Dies ist aber leicht zu bewerkstelligen. Wir benötigen dazu zwei Indices - i und j. i zeigt dabei auf das erste Element in F1 und j in das erste Element in F2. Nun wird F1[i] mit F2[j] verglichen. Ist F1[i] kleiner wird dieses in F eingetragen und i um eins erhöht, andernfalls tragen wir F2[j] in F ein und inkrementieren j. So verfahren wir bis entweder i oder j das Ende der jeweiligen Folge überschreitet. In diesem Falle hängen wir noch alle Elemente der jeweilgen anderen Folge an F an und sind fertig. Die Verschmelzung läßt sich also bequem und schnell in einem Durchgang durch die beiden Teilfolgen bewerkstelligen.

Wenn Sie sich das Mergesort-Programm in Listing 4 genauer ansehen, werden Sie bemerken, daß Mergesort die gegebene Liste einmal in zwei Teilfolgen unterteilt. Jede von diesen wird dann wieder in zwei weitere unterteilt usw. Diese Unterteilung geht soweit, daß jede Folge nur mehr ein einziges Element enthält, das nicht mehr aufgeteilt werden kann. Diese Folgen der Länge eins kann man jede für sich prinzpiell als sortiert betrachten. Die Sortierung erfolgt beim Mergesort also im Prinzip implizit durch wiederholtes Aufteilen der Folgen. Diese N "sortierten" Einser-Folgen werden dann zu N/2 Folgen der Länge zwei verschmolzen, wobei jede dieser Zweier-Folgen in sich sortiert bleibt. Aus den N/2 Zweierfolgen werden durch weitere Verschmelzungen N/4 Viererfolgen bis schlußendlich die letzten beiden N/2-Folgen zu einer sortierten N-Folge verschmolzen werden. Die letzten beiden Sortierverfahren sind sicherlich recht kompliziert, aber auch die schnellsten. Obwohl Quicksort beispielsweise im schlechtesten Fall (worst case) genauso schlecht sein kann wie Sortieren durch Suchen, nämlich genau dann, wenn zufällig das größte Element der Liste als Pivotelement gewählt wird. Trotzdem benötigt es im Durchschnitt (average case) viel weniger Zeit als sein einfacher Konkurrent. Das Studium der letzten beiden Algorithmen lege ich Ihnen auch dann ans Herz, wenn Sie nicht vorhaben, jemals ein anderes Sortierverfahren als das "eingebaute" qsort zu benutzen. Sie zeigen vorbildlich auf, wie relativ einfach schwierige Probleme durch geniale Programmiertechniken und Rekursion gelöst werden können. Denn wie lautet ein bekannter Ausspruch: "Iteration ist menschlich, Rekursion ist göttlich!"

Workshop Teil 5

Listing 6-1 (ASCII;1KB)

Listing 6-2 (ASCII;1KB)

Listing 6-3 (ASCII;1KB)

Listing 6-4 (ASCII;1KB)