Algorithmen und Datenstrukturen in PASCAL Teil 9: Sortiermethoden B
Wie bereits in der letzten Folge angekündigt, werde ich mich heute mit den beiden Sortieralgorithmen "Heapsort" und "Quicksort" befassen. Wie sich herausstellen wird, handelt es sich dabei um Sortieralgorithmen der Ordnung O(n*log(n)) (jedenfalls im durchschnittlichen Fall). Diese Begebenheit geht, nicht nur auf dem Papier, mit einer gewaltigen Effizienzsteigerung, gegenüber den Algorithmen der letzten Folge, einher.
Heapsort
Beginnen möchte ich mit Heapsort. Sein Schöpfer, J. Williams, hatte dabei als grundlegenden Gedanken, daß man einen Array, entsprechende Vereinbarungen vorausgesetzt, auch als Baum interpretieren kann. Dabei beginnt man mit dem ersten Arrayelement, welches synomym mit der Wurzel verwendet wird, gefolgt von den beiden Wurzelnachfolgern (2. und 3. Arrayelement) und sofort ...
Man erhält, daß man den linken Nachfolger eines Array-, bzw. Baumelementes, durch Multiplikation des Arrayindex mit 2 erhält (2i) und den rechten Nachfolger entsprechend durch 2i+1.
Ein Beispiel für diesen Interpretationsvorgang finden Sie zu Beginn und zum Ende der Abbildung 9f).
Das Ziel ist es nun diesem Baum eine Struktur zu geben, die Informationen über die Elementabfolge, auch über das Ausfügen eines einzelnen Elementes hinaus, bewahrt. Dazu definierte Williams die Struktur des Heap, genauer die des Maximumheap und des Minimumheap.
Für einen Maximumheap gilt, daß jeder Vater im Baum einen größeren Schlüssel als seine (maximal) zwei Söhne besitzt. In der Arraynotation müßte also gelten:
a[i]>=a[2*i] und a[i]>=a[2*i+1],
soweit die a[2i] bzw. a[2i+1] überhaupt vorhanden sind.
Entsprechend gilt für den Minimumheap:
a[i]<=a[2*i] und a[i]<=a[2*i+1].
Eine Eigenschaft, die sich für einen Maximumheap (Minimumheap) sofort ablesen läßt, ist die Tatsache, daß sich das größte (kleinste) Arrayelement in Position a[1] befindet. Ein Algorithmus, auf der Basis der Heaps, könnte also etwa folgendes Aussehen haben:
- Überführe unstrukturierten Array in Maximumheap.
- Solange noch Elemente im Heap vorhanden sind
a. Vertausche erstes und letztes Arrayelement.
b. Füge letztes Element aus Heap aus (Dekrementiere linke Grenze)
c. Korrigiere Heapeigenschaft
Dadurch rückt das Maximum (Minimum) an die letzte Arrayposition und ein aufsteigend (absteigend) sortiertes Array wird nach und nach von hinten aufgebaut.
In der Praxis (Programmierung) sieht dies so aus, daß man eine Prozedur korrigiere zur Korrektur der Heapeigenschaften an einer Stelle a[i] verwendet. Dabei wird a[i] mit a[2i] und a[2i+1] verglichen und entsprechend den Heapanforderungen ausgetauscht. Dies macht dann eine weitere Heapüberprüfung in dem betroffenen Teilzweig (entweder a[2i], oder a[2i+1]) notwendig, wofür in der Prozedur korrigiere (Listing 9a, Zeilen 12-41) das zentrale WHILE- Statement benutzt wird.
Wendet man nun korrigiere nacheinander auf die Knoten (max DIV 2) bis hin zu 1 an, so erhält man, aus einem unstrukturierten Array, einen Heap (Heapsort, Zeilen 46-52). Wird dann zusätzlich über alle Arrayelemente geschleift und in dieser Schleife die erste Arrayposition mit dem jeweiligen Arrayende vertauscht, sowie der Heap entsprechend korrigiert (Zeilen 53-60), ist Heapsort fertig.
Die Wirkungsweise von Heapsort möchte ich Ihnen noch an der Abbildung 9f) verdeutlichen. Hier sehen Sie Heapsort bei der Arbeit. Angefangen mit einem unstrukturierten Array von sieben Elementen (1 6 2 5 9 0 7), wird in den ersten vier Schritten zunächst die Heapeigenschaft herbeigeführt. In oben beschriebener Wechselwirkung, des Ausfügens eines Elementes und der Heapkorrektur, wird nun, nacheinander, jedes Element aus dem Heap ausgefügt, bis schließlich ein vollständig sortiertes Array erzeugt ist (0 1 2 5 6 7 9).
Ein etwas größeres Beispiel finden Sie in Abbildung 9a), hier allerdings nur mit unserer 'Schnappschußausgabe'. Dummerweise konnte ich mich nicht motivieren, Ihnen diesen Sortiervorgang als Baumabfolge aufzuzeichnen, wofür Sie sicherlich Verständnis aufbringen.
Abbildung 9a: Heapsort
54 22 66 89 72 58 11 49 30 96 93 91 44 82 65 54 22 66 89 72 58 82 49 30 96 93 91 44 11 65 54 22 66 89 72 91 82 49 30 96 93 58 44 11 65 54 22 66 89 96 91 82 49 30 72 93 58 44 11 65 54 22 66 89 96 91 82 49 30 72 93 58 44 11 65 54 22 91 89 96 66 82 49 30 72 93 58 44 11 65 54 96 91 89 93 66 82 49 30 72 22 58 44 11 65 96 93 91 89 72 66 82 49 30 54 22 58 44 11 65 93 89 91 65 72 66 82 49 30 54 22 58 44 11 96 91 89 82 65 72 66 11 49 30 54 22 58 44 93 96 89 72 82 65 54 66 11 49 30 44 22 58 91 93 96 82 72 66 65 54 58 11 49 30 44 22 89 91 93 96 72 65 66 49 54 58 11 22 30 44 82 89 91 93 96 66 65 58 49 54 44 11 22 30 72 82 89 91 93 96 65 54 58 49 30 44 11 22 66 72 82 89 91 93 96 58 54 44 49 30 22 11 65 66 72 82 89 91 93 96 54 49 44 11 30 22 58 65 66 72 82 89 91 93 96 49 30 44 11 22 54 58 65 66 72 82 89 91 93 96 44 30 22 11 49 54 58 65 66 72 82 89 91 93 96 30 11 22 44 49 54 58 65 66 72 82 89 91 93 96 22 11 30 44 49 54 58 65 66 72 82 89 91 93 96 11 22 30 44 49 54 58 65 66 72 82 89 91 93 96
Quicksort (rekursiv)
Der Quicksortalgorithmus, entwickelt von Hoare, ist DER Algorithmus, der die Methode des Sortierens durch Austauschen charakterisiert. Obwohl er sehr einfach und somit schnell zu beschreiben ist, ist er, in der Praxis, die beste bekannte Sortiermethode.
Erster Schritt des Quicksortalgorithmus, ist die Auswahl eines beliebigen Arrayelementes, das wir als Pivotelement, oder kurz pivot, bezeichnen wollen. Alle Arrayelemente, kleiner diesem Element, werden dann auf die linke Seite des Arrays befördert, alle größeren Elemente auf die rechte Seite. Es entstehen zwei Teilarrays, a[1]..a[j] und a[i]..a[max], für die gilt:
a[x]<=a[y], für alle x aus 1..j und alle y aus i..max, wobei j=i-1 ist.
Durch Anwendung von Quicksort auf die so entstehenden beiden Teilarrays erreicht man, indem man die Arraylänge bis auf eins herunterspielt, ein sortiertes Gesamtarray.
Realisiert finden Sie eine rekursive Variante des Quicksortalgo-rithmus im Listing 9b). Als Pivotelement wird hier genau das mittlere Element des Teilarrays (l..r) gewählt. Die REPEAT-Schleife realisiert nun die Zerlegung des Teilarrays. Zu diesem Zweck werden zwei Zeiger, i und j, von links und rechts über das Array geschoben und, bei Bedarf, werden zwei Elemente ausgetauscht.
Nach Abbruch dieses Vorgangs sind nun nur noch zwei rekursive Aufrufe, mit den neuen Teilarraygrenzen l..j und i..r zu tätigen, natürlich nur, soweit es sich dabei noch um Teilarrays handelt (l<j, bzw. i<r).
Der 'Knackpunkt' am Quicksort-Algorithmus ist die geeignete Auswahl des Pivotelementes. Hat man nämlich Pech, so erwischt man ein Pivotelement, was eine sehr ungleichmäßige Aufspaltung der beiden Teilarrays zur Folge hat. Im Extremfall führt dies zu einem 1-elementigen Teilarray und einem (max-1)-elementigen Teilarray. Hält das Lospech an, so darf man Quicksort eigentlich nicht mehr als quick bezeichnen.
'Gut und schön, aber sehr unwahrscheinlich' werden Sie vielleicht sagen, allerdings, ganz so unwahrscheinlich ist dieser schlechteste Fall nicht, wie das untenstehende Beispiel zeigt:
Als Pivotelement wählen wir gerade das erste Element des Teilarrays. Wenden wir nun den Algorithmus auf ein schon sortiertes, oder teilsortiertes, Array an, so passiert folgendes:
Im Falle des schon sortierten Arrays, geschieht gerade die Katastrophe, Quicksort zerlegt jedesmal den Array in ein 1-elementiges Teilarray und Rest. Im Falle eines teilsortierten Arrays, dürfte auch nichts besonders Anschauliches herauskommen.
Gerade diesem Mißstand beugen wir in unserer Implementierung 9b) vor, indem wir immer das mittlere Element eines Arrays als Pivotelement wählen. Nichtsdestotrotz kann natürlich auch hier die Katastrophe eintreten ...
Für ganz Vorsichtige empfiehlt es sich deshalb, aus einer gewissen Anzahl von Arrayelementen das Mittlere auszuwählen. In diesem Fall dürfte Murphy eindeutig verloren haben. Man sollte hierbei allerdings darauf achten, daß die Anzahl der Auswahlelemente nicht zu groß wird, weil das wieder den Algorithmus bremst.
Nun noch ein Beispiel (Abbildung 9b). Sie sehen Quicksort angewendet auf unsere Standardfolge. Das Pivotelement habe ich Ihnen jeweils mit einem 'v' gekenn-zeichnet. Die Teilarrays sind durch '¦' voneinander abgeschottet und die überstrichenen Teilarrays '_' kennzeichnen den Teil der Arbeit, der bereits abgeschloßen ist.
Abbildung 9b: Quicksort
v
54 22 66 89 72 58 11 49 30 96 93 91 44 82 65
v
44 22 30 49 11 ¦ 58 72 89 66 96 93 91 54 82 65
v
11 22 30 ¦ 49 44 ¦ 58 72 89 66 96 93 91 54 82 65
__________ v
11 22 30 ¦ 49 44 ¦ 58 72 89 66 96 93 91 54 82 65
__________________ v
11 22 30 ¦ 44 49 ¦ 58 72 89 66 96 93 91 54 82 65
__________________ v ____
11 22 30 ¦ 44 49 ¦ 58 72 89 66 65 93 91 54 82 ¦ 96
__________________ v ____
11 22 30 ¦ 44 49 ¦ 58 54 65 ¦ 66 89 93 91 72 82 ¦ 96
_______________________ v ____
11 22 30 ¦ 44 49 ¦ 54 ¦ 58 65 ¦ 66 89 93 91 72 82 ¦ 96
_________________________________ v ____
11 22 30 ¦ 44 49 ¦ 54 ¦ 58 ¦ 65 ¦ 66 89 93 91 72 82 ¦ 96
_________________________________ v _________
11 22 30 ¦ 44 49 ¦ 54 ¦ 58 ¦ 65 ¦ 66 89 82 91 72 ¦ 93 ¦ 96
_________________________________ v _________
11 22 30 ¦ 44 49 ¦ 54 ¦ 58 ¦ 65 ¦ 66 72 82 ¦ 91 89 ¦ 93 ¦ 96
______________________________________________ v _________
11 22 30 ¦ 44 49 ¦ 54 ¦ 58 ¦ 65 ¦ 66 72 ¦ 82 ¦ 91 89 ¦ 93 ¦ 96
________________________________________________________________
11 22 30 ¦ 44 49 ¦ 54 ¦ 58 ¦ 65 ¦ 66 72 ¦ 82 ¦ 89 ¦ 91 ¦ 93 ¦ 96
Quicksort (iterativ)
Wegen der enormen Wichtigkeit des Quicksortalgorithmus, gebe ich Ihnen noch eine iterative (nicht rekursive) Realisierung dieses Algorithmus an. Im Unterschied zur rekursiven Variante, haben wir nun den Stack für die Parameter (linke und rechte Arraygrenze) selbst zu verwalten.
Halt, da war doch was
Richtig, Stacks kennen wir bereits aus der ersten Folge! Was also liegt näher als die Routinen von damals zu benutzen. Kramen Sie also am besten noch einmal Ihre ST 10/87 raus und lesen da nach !
Fertig " Gut ! Die stack_data bestehen heute, entgegen den damaligen Ausführungen, nicht aus einem Integer, sondern gleich aus einem RECORD von zwei Integern, der die jeweiligen Arraygrenzen, l und r, aufnimmt. Außerdem muß die Operation top, weil unsere Stackdaten nicht mehr von einem einfachen Typ (sondern RECORD) sind, prozedural formuliert werden. Die notwendigen Änderungen finden Sie anliegend.
In Quicksort selbst (Listing 9c) sind kaum Änderungen notwendig. Zunächst müssen zwei Variablen, x vom Typ stack und el vom Typ stack_data, in die Variablendeklaration aufgenommen werden. Die rekursive Subprozedur sort entfällt, da ihre Arbeit von der Hauptprozedur übernommen wird. Stattdessen werden, zu Beginn der Prozedur Quicksort, die maximalen Arraygrenzen, 1..max, auf den Stack abgelegt. Zu den Anweisungen von Quicksort (rekursiv), gesellt sich nun noch eine alles umschließende REPEAT-Schleife hinzu, die solange zu durchlaufen ist, bis der Parameterstack leer wird. Vor Ausführung des Kernstückes von Quicksort, sind nun noch die Parameter vom Stack zu holen. Nach Ausführung ist, statt den beiden rekursiven Aufrufen, ein Abstacken der jeweiligen Arraygrenzen notwendig.
Und das ist auch das generelle Strickmuster, mit dem rekursive Prozeduren obiger Machart in iterative Prozeduren & Stacks umgewandelt werden.
A: Ersetze jeden Aufruf der Funktion durch ein Abstacken der zugehörigen Parameter (push)
B: Hole, vor Ausführung der Operation, die Daten vom Stack (top, pop).
C: Schließe die eigentliche Funktion durch eine REPEAT ... UNTIL is_empty(x); Schleife ein.
Als Bedingung für das Gelingen dieser Umwandlung, muß allerdings gelten, daß die umzuwandelnden, rekursiven Operationen mit den rekursiven Aufrufen abgeschloßen werden. Dies kann man bei den meisten, zumindestens bei den einfacheren, rekursiven Operationen durch leichte Umformungen erreichen.
Noch einmal Quicksort, oder Bestsort
Einer der Nachteile sämtlicher 'höherer' Sortierverfahren, zu denen auch der gerade behandelte Quicksortalgorithmus zählt, ist ihr schlechtes Verhalten bei kleinen Arrays. (Unter einem kleinen Array verstehe ich hier ein Array mit Größe weit unter 100, beispielsweise 20.) Direkt läßt sich diese Tatsache leider sehr schlecht nachprüfen, da die auftretenden zeitlichen Größen, bei kleinen Arrays und dermaßen 'quicken' Sortiermethoden, weit außerhalb unseres Zwei-Sekunden-Systemzeittaktes liegen.
Indirekt kann man die Zeitunterschiede allerdings gut nachprüfen, indem man einen Quicksortalgorithmus entwickelt, der bei Arrays unterhalb einer gewissen Länge auf ein 'einfaches' Sortierverfahren, beispielsweise das direkte Einfügen, umschaltet. Dieser Algorithmus sollte dann, bei großen Arrays, eine meßbare positive Abweichung vom normalen Quicksort zeigen, da eine höhere Methode 'fürs Grobe' benutzt wird und in einem Bereich, wo diese Methode nicht mehr so günstig ist, umgeschaltet wird.
Ein angenehmer Nebenaspekt dieser Überlegung ist die Tatsache, daß man dadurch eine Sortiermethode erhält, die schneller als das reine Sortieren mit Quicksort ist, was ich durch die Verwendung der Bezeichnung Bestsort unterstreiche.
Will man diese Überlegungen in unsere Sortiermethode 9b) einbeziehen, so werden hier folgende Änderungen notwendig: Aufbauend auf der rekursiven Prozedur sort, ist bei den Aufrufen von sort, tritt eine Unterschreitung eines gewissen Längen-schwellwertes (toggle) auf, in eine einfache Sortiermethode zu verzweigen. Im Listing 9d) habe ich dazu direktes_einfuegen gewählt, was sich vom Listing 8a), der letzten Folge, lediglich durch flexible Arraygrenzen unterscheidet. Für die letzendliche Geschwindigkeit ist die Größe von toggle von entscheidender Bedeutung. Meine Messungen haben ergeben, daß ich mit einem Wert von 20 sehr gut liege. Dies ist auch der Wert, der den Zeitmessungen zugrunde liegt.
Um bei unserem Beispielarray diese spezielle Sortiermethode zur Geltung zu bringen, müssen wir mit toggle auf 5 runtergehen, da bei toggle = 20 und einer Arraylänge von 15 das Verfahren ein reines direktes_einfuegen wäre. In der Abbildung 9c) sehen Sie das daraus resultierende Verhalten:
Abbildung 9c: Bestsort
v
54 22 66 89 72 58 11 49 30 96 93 91 44 82 65
v
44 22 30 49 11 ¦ 58 72 89 66 96 93 91 54 82 65
22 44 30 49 11
22 30 44 49 11
22 30 44 49 11
______________
11 22 30 44 49
v ____
¦ 58 72 89 66 65 93 91 54 82 ¦ 96
58 54 65
54 58 65
________
54 58 65
66 89 93 91 72 82
66 89 93 91 72 82
66 89 91 93 72 82
66 72 89 91 93 82
_________________
66 72 82 89 91 93
Beginnend mit einer Zerlegung des Gesamtarrays, zerfällt unser Beispiel gleich in zwei Teile, die unterschiedliches Verhalten aufweisen. Im ersten Teil wird mit direktes_einfuegen sortiert und im zweiten Teil mit Quicksort weitergearbeitet. So fortgesetzt, ergibt sich, unter Verwendung der jeweiligen Sortiermethode, ein sortiertes Gesamtarray. Die, für die Sortierung nicht wichtigen Arrayelemente, habe ich diesmal, zwecks Übersichtlichkeit, entfernt.
Testumgebung
Wie ich letztes Mal bereits erwähnte, wurde die Testumgebung Listing 8f) ebenfalls hinsichtlich der heutigen Sortierverfahren entwickelt. Dummerweise ergeben sich gut meßbare Sortierzeiten, bei den heutigen Prozeduren, erst bei Elementanzahlen in einer Größenordnung von 10000, was im Listing 8f) folgende Änderungen bedingt:
Die ARRAY-Grenze für den ARRAY a in field ist auf mindestens 64000 hochzusetzen. Zusätzlich muß noch die Compileroption {$I+}, vor Beginn des PROGRAM- Statements der Testumgebung, gesetzt werden, womit wir unserem Pascal+ Compiler mitteilen, daß wir die Bezeichnung Integer synonym für Long_Integer verwenden möchten. Diese Änderung wurde notwendig weil die, normalerweise zur Indizierung der Arrays benutzten, einfachen (!) Integerwerte den Testarray nicht mehr überdecken können, was unfairerweise in einer Endlosschleife enden würde. Ästhetiker sollten auch noch die entsprechenden Hinweise auf Elementbeschränkungen im Programm ändern.
Vergleiche
Unter all diesen Änderungen, ergeben sich für die vier Algorithmen der heutigen Folge die Sortierzeiten der Abbildung 9d).
Abbildung 9d: Sortierzeitmessungen (in Sekunden)
- Random-Array
Elemente Heapsort Quicksort#1 Quicksort#2 Bestsort __________________________________________________________ 8000 8 6 6 4 16000 18 12 14 10 32000 38 22 30 20 64000 78 52 68 44
- Aufsteigend sortiertes Array
Elemente Heapsort Quicksort#1 Quicksort#2 Bestsort __________________________________________________________ 8000 8 2 4 2 16000 18 6 8 4 32000 38 12 16 8 64000 82 28 36 20
- Absteigend sortiertes Array
Elemente Heapsort Quicksort#1 Quicksort#2 Bestsort __________________________________________________________ 8000 8 4 4 2 16000 16 6 8 4 32000 36 12 18 10 64000 76 28 38 22
Heapsort schneidet hier vergleichsweise schlecht ab, ist aber immerhin noch enorm schnell, verglichen mit den letztmaligen Prozeduren.
Quicksort (rekursiv) besitzt einen leichten Vorteil gegenüber Quicksort (iterativ), was wohl durch den erhöhten Aufwand für die Selbstverwaltung des Parameterstacks zu erklären ist.
Bestsort stellt alles in den Schatten und erweist sich als würdige Verbesserung von Quicksort.
Anzumerken ist ebenfalls noch, daß bei keinem meiner Testläufe mit Quicksort die mögliche Katastrophe, also eine sehr lange Sortierzeit, stattgefunden hat.
Die graphische Auswertung der gemessenen Werte finden Sie in Abbildung 9e). Bemerkenswert ist, daß sämtliche Algorithmen eine kaum meßbare, allerdings vorhandene, Steigung im Verhältnis Elemente/Zeit aufweisen. Eine genauere Meßmethode, oder einige mathematische Überlegungen, die ich Ihnen und mir an dieser Stelle ersparen möchte, würden ergeben, daß alle vier Algorithmen eine Ordnung von O(nlog(n)) besitzen. Dabei sind die Quicksortalgorithmen noch einmal gesondert zu betrachten, da die oben erwähnte Katastrophe, also die Abspaltung in sehr kleine und sehr große Teilarrays bei der Zerlegung, die Ordnung O(n2) besitzen würde. Daher auch die Bezeichnung 'unechter' O(nlog(n)) in Abbildung 9e).
Dieser schlechteste Fall kommt, in der Praxis, aber so gut wie nie vor, wie die untenstehende Überlegung zeigt:
Die Wahrscheinlichkeit bei Quicksort immer eines der beiden schlechtesten Pivotelement auszuwählen, berechnet sich nämlich, bei einem reinen Zufallsarray, gerade zu 2n/n!. Wie Sie aus der Betrachtung der Fakultätsfunktion im Abschnitt über die Potenzreihen bereits wissen, wird bereits bei sehr kleinen n n! sehr groß. Da 2n dieser Steigerung nichts entgegen zu setzen hat, wird, wie folgendes Zahlbeispiel zeigen wird, 2n/n! sehr klein. Bereits bei nur fünfzehn Arrayelementen ergibt siche eine Wahrscheinlichkeit für den schlechtesten Fall, die weit unterhalb der eines Lottosechser liegt (0.0000025058%). Also auch kein besonderer Wermutstropfen im Quicksortkelch.
Vorausschau
In der letzten Folge von Algorithmen & Datenstrukturen werde ich Sortierverfahren vorstellen, die für das Sortieren auf externen Medien geeignet sind, teilweise aber auch brauchbare interne Verfahren darstellen. Begriffe, in diesem Kontext, sind das 'Sortieren mit Bändern', sowie Mergesort.
Dirk Brockhaus