Algorithmen und Datenstrukturen in PASCAL Teil 8: Sortiermethoden A

Nachdem ich nun die Datenverarbeitung glücklich hinter mich gebracht habe, möchte ich den letzten großen Abschnitt dieser Artikelserie einer Klasse von Algorithmen widmen, die praktisch für jede Art Anwendung unentbehrlich sind. Ich spreche von Sortieralgorithmen. Dabei meine ich nicht die Art von Sortierung, die wir in den letzten Folgen durch Einordnung in irgendeine Art von Informationsstruktur erreicht haben, sondern die gleichzeitige Sortierung einer großen Anzahl von Elementen auf möglichst schnelle Weise. Wie Sie sehen werden ist dabei der Weg vom einfachen Ansatz, bis zu einem anspruchsvollen (schnellen) Programm weit.

Motivation

Die Sortierung von größeren Datenmengen ist eines der wenigen Gebiete in der Informatik, wo es sehr leicht möglich ist, direkte Vergleiche zwischen einzelnen Algorithmen, in Form von Zeitmessungen, anzustellen. Diese quasi Wettkampfsituation hat eine große Anzahl von unter-schiedlichen Algorithmen zu Tage gefördert, indem immer wieder irgendwelche Informatiker versuchten, die Algorithmen ihrer Konkurrenz zur Strecke zu bringen.

Um in etwa dieser Entwicklung Rechnung zu tragen, werde ich Ihnen in dieser und den zwei folgenden Teilen dieser Serie, beginnend mit den 'auf der Hand liegenden' Algorithmen, bis hin zu den klassischen Sortieralgorithmen, eine kurze Zusammenfassung presentieren.

Ich hoffe, daß ich Ihnen, mit den dabei angestellten Zeitmessungen, Impulse für DEN, von Ihnen selbst zu entwickelnden, Superalgorithmus, nennen wir ihn hypersort, geben kann. Leider muß ich gestehen, daß meine persönlichen Bemühungen nicht ausreichten den momentanen Spitzenreiter (quicksort) zu erreichen.

Ansätze

Bei der Sortierung sind grundsätzlich immer zwei mögliche Ausgangssituationen zu beachten: Entweder liegen die Daten in einer Filestruktur vor und müßen auf sequentielle Weise sortiert werden, oder wir haben eine Representation in Arrays vorliegen und können so beliebig auf die Komponenten zugreifen. Mit dem häufiger vorliegenden, letzteren Fall werden wir heute beginnen.

Die Representation der Daten erfolgt in einer Type field, die im Wesentlichen den Array a der Schlüssel enthält. Weiterer Bestandteil dieses field ist lediglich ein Zeiger auf das letzte Arrayelement (max), um auch variable Feldgrößen verarbeiten zu können. Wir gehen dabei davon aus, daß der zu sortierende Anteil des Arrays im Bereich 1..max liegt. Die entsprechende Pascal- Notation finden Sie in den Zeilen 12-15 des Listings 8f).

Um nun einen solchen Array zu sortieren, unterscheidet man prinzipiell zwischen vier Methoden, die aber in den meisten Fällen keine ganz eindeutige Klassifizierung erlauben:

  1. Sortieren durch Einfügen

Ein Element wird in ein schon sortiertes Array von Elementen eingefügt. Beginnend mit dem ersten Element des Arrays, was ja wohl zwangsläufig sortiert ist, wird nacheinander, durch Einfügen der restlichen Array-Elemente, eine sortierte Folge aufgebaut.

  1. Sortieren durch Auswählen

Das Minimum des Arrays wird ausgewählt und an die erste Position gebracht. Durch wiederholte Anwendung dieses Vorgangs wird das gesamte Array sortiert.

  1. Sortieren durch Austauschen

Zwei, nicht notwendigerweise, benachbarte Elemente werden gemäß der Ordnungsrelation ausgetauscht. Dieses Verfahren wird solange vorgenommen, bis keine Vertauschungen mehr stattfinden können.

  1. Sortieren durch Mischen

Zwei oder mehr sortierte Quellarrays werden miteinander verschmolzen, indem das Minimum der vordersten Arraypositionen in einen Zielarray kopiert wird. Diese Methode ist auch die einzige, die sich leicht auf Files übertragen läßt, doch damit beschäftigen wir uns später.

Direktes Einfügen

Zunächst betrachten wir einmal einen Algorithmus der einer von den zweien 'auf der Hand liegenden' Algorithmen ist: Das Sortieren durch direktes Einfügen.

Wir gehen davon aus, daß wir einen bereits sortierten Array im Bereich 1..i-1 vorliegen haben und ein noch unsortiertes Teilstück im Bereich i..max. In diesem Fall fügen wir in den sortierten Bereich das Element a[i] ein, indem wir den sortierten Teilarray bis zu dem Punkt, wo seine Elemente kleiner werden als unser einzufügendes Element, um eine Position nach rechts schieben. Das Element a[i] wird dann in die frei werdende Stelle eingefügt.

Diesen Algorithmus des 'direkten Einfügens' finden Sie im Listing 8a) realisiert.

Die Abbildung 8a) zeigt direktes_einfuegen bei der Arbeit. Dazu ist eine kleine Hilfsroutine zur Arrayausgabe notwendig, die man am Ende der FOR-Schleife in den Algorithmus einschmuggelt.

Abbildung 8a: Direktes Einfuegen

68 
 77 28 35 95 58 40 2 99 82 51 78 49 61 31
68 77 
 28 35 95 58 40 2 99 82 51 78 49 61 31
28 68 77 
 35 95 58 40 2 99 82 51 78 49 61 31
28 35 68 77 
 95 58 40 2 99 82 51 78 49 61 31
28 35 68 77 95 
 58 40 2 99 82 51 78 49 61 31
28 35 58 68 77 95 
 40 2 99 82 51 78 49 61 31
28 35 40 58 68 77 95 
 2 99 82 51 78 49 61 31
2 28 35 40 58 68 77 95 
 99 82 51 78 49 61 31
2 28 35 40 58 68 77 95 99 
 82 51 78 49 61 31
2 28 35 40 58 68 77 82 95 99 
 51 78 49 61 31
2 28 35 40 51 58 68 77 82 95 99 
 78 49 61 31
2 28 35 40 51 58 68 77 78 82 95 99 
 49 61 31
2 28 35 40 49 51 58 68 77 78 82 95 99 
 61 31
2 28 35 40 49 51 58 61 68 77 78 82 95 99 
 31
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99 

Beispielsweise:

FOR l:=1 TO feld.max DO write(feld.a[l]);

Dadurch werden gewissermaßen Schnappschüsse des Arrays, während der einzelnen Sortierphasen, erstellt.

Man sieht wie, von links beginnend, die sortierte Folge immer länger wird und schließlich den gesamten Array ausmacht.

Direkte Auswahl

Der andere 'naheliegende' Algorithmus ist die direkte Auswahl des Minimums. Der Array wird dazu, auf der Suche nach dem Minimum, bis zum Ende durchlaufen. Die so ermittelte Stelle wird mit dem ersten Element vertauscht und man erhält ein, um ein Element vergrößertes, sortiertes Teilstück. Dieser Algorithmus wurde im Listing 8b) realisiert. Wenn wir ihn auf die gleiche Folge, wie oben anwenden, so ergeben sich die Arbeitsschritte der gleichnamigen Abbildung.

Abbildung 8b: Direkte Auswahl

 68 77 28 35 95 58 40 2 99 82 51 78 49 61 31
2 
 77 28 35 95 58 40 68 99 82 51 78 49 61 31
2 28 
 77 35 95 58 40 68 99 82 51 78 49 61 31
2 28 31 
 35 95 58 40 68 99 82 51 78 49 61 77
2 28 31 35 
 95 58 40 68 99 82 51 78 49 61 77
2 28 31 35 40 
 58 95 68 99 82 51 78 49 61 77
2 28 31 35 40 49 
 95 68 99 82 51 78 58 61 77
2 28 31 35 40 49 51 
 68 99 82 95 78 58 61 77
2 28 31 35 40 49 51 58 
 99 82 95 78 68 61 77
2 28 31 35 40 49 51 58 61 
 82 95 78 68 99 77
2 28 31 35 40 49 51 58 61 68 
 95 78 82 99 77
2 28 31 35 40 49 51 58 61 68 77 
 78 82 99 95
2 28 31 35 40 49 51 58 61 68 77 78 
 82 99 95
2 28 31 35 40 49 51 58 61 68 77 78 82 
 99 95
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99 

Bubblesort #1

Ein Algorithmus mit recht lustigem Namen ist Bubblesort. Den Array von hinten durchlaufend, werden jeweils, wenn erforderlich, zwei benachbarte Elemente ausgetauscht. Diese Prozedur wird bis zum Array-Anfang durchgeführt, womit wir mindestens das Minimum an die erste Position gebracht haben, einige andere größere Elemente aber wahrscheinlich näher ans Ziel gerückt sind.

So erklärt sich auch der Name, indem man, zugegebenermaßen mit einiger Phantasie, die Array-Elemente als Blasen auffaßt, die gegen ihren Bestimmungsort im Array aufsteigen.

Die Prozedur finden Sie im Listing 8c) realisiert. Der zugehörigen Abbildung können Sie leicht entnehmen, ob Sie die nötige Phantasie für die Akzeptanz der Namensgebung aufbringen.

Abbildung 8c: Bubblesort #1

68 77 28 35 95 58 40 2 99 82 51 78 49 61 31
2 68 77 28 35 95 58 40 31 99 82 51 78 49 61
2 28 68 77 31 35 95 58 40 49 99 82 51 78 61
2 28 31 68 77 35 40 95 58 49 51 99 82 61 78
2 28 31 35 68 77 40 49 95 58 51 61 99 82 78
2 28 31 35 40 68 77 49 51 95 58 61 78 99 82
2 28 31 35 40 49 68 77 51 58 95 61 78 82 99
2 28 31 35 40 49 51 68 77 58 61 95 78 82 99
2 28 31 35 40 49 51 58 68 77 61 78 95 82 99
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99 <- ab hier finden 
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99  keine Vertauschungen
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99  mehr statt
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99

Bubblesort #2

In der Abbildung 8c) läßt sich ebenfalls absehen, daß einige Sortierdurchgänge ohne Änderungen stattfinden (markierte Stelle). Eine leichte Änderung von Bubblesort schafft Abhilfe, indem ein Flag mit aufgenommen wird, welches sich die Vertauschung von Elementen merkt. Hat in einem Durchgang keine Vertauschung stattgefunden, so kann der Algorithmus abgebrochen werden. (Listing und Abbildung 8d)

Abbildung 8d: Bubblesort #2

68 77 28 35 95 58 40 2 99 82 51 78 49 61 31
2 68 77 28 35 95 58 40 31 99 82 51 78 49 61
2 28 68 77 31 35 95 58 40 49 99 82 51 78 61
2 28 31 68 77 35 40 95 58 49 51 99 82 61 78
2 28 31 35 68 77 40 49 95 58 51 61 99 82 78
2 28 31 35 40 68 77 49 51 95 58 61 78 99 82
2 28 31 35 40 49 68 77 51 58 95 61 78 82 99
2 28 31 35 40 49 51 68 77 58 61 95 78 82 99
2 28 31 35 40 49 51 58 68 77 61 78 95 82 99
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99
2 28 31 35 40 49 51 58 61 68 77 78 82 95 99 <- Erst in der ersten
                                              Zeile ohne
                                              Vertauschungen
                                              Merkt Bubblesort
                                              #2, dass es fertig
                                              ist.

Sicherlich ist es bei dem Bubblesort Algorithmus und bei den beiden 'einfachen' Algorithmen sehr leicht möglich noch weitere Verbesserungen anzugeben, beispielsweise könnte man bei der direkten Auswahl auch gleichzeitig mit dem Minimum das Maximum bestimmen. Wie die Sortierzeittestes aber ergeben werden, spielen alle diese Algorithmen nur eine untergeordnete Rolle, da sie bei großen Arrays viel zu langsam sind. Deshalb schenke ich mir weitergehende Verbesserungen.

Shellsort

Anders ist das beim 1959 von D.L.Shell entwickelten Algorithmus shellsort. Shell ging davon aus, daß zunächst weiter auseinanderliegende Arrayelemente (Abstand k) verglichen und sortiert werden. Durch Reduzierung von k und abermaligen Austausch, werden dadurch immer enger zusammenstehende Elemente verglichen. Letztendlich schließt shellsort mit k=1 und dem Vergleich benachbarter Elemente ab. Dies entspricht dann dem gewöhnlichen Sortieren.

Am besten macht man sich das an einem Beispiel, vorzugsweise unserem Standardbeispiel aus den vorhergehenden Abbildungen, klar. Das Resultat sehen Sie in Abbildung 8e). Die dabei vorgegebene Schrittfunktion lautet:

Für unser Beispiel (max=15) führt dies zur Folge k=7,3,1. Zu Beginn, mit k=7, sind die jeweils sieben Positionen auseinanderliegenden Elemente

(68,2) ; (77,99) ; (28,82) ; (35,51) ; (95,78) ; (58,49) ; (40,61) und (31;68)

zu vergleichen, wobei jeweils das Minimum der zwei Elemente nach vorn rückt. Durch Fortführung des Verfahrens, gelangt man schließlich zu k=1 und somit zum gewöhnlichen Sortieren. Dabei ist allerdings zu beachten, daß hier kaum noch Vertauschungen stattfinden, weil die vorhergehenden Stufen schon eine beträchtliche Vorarbeit geleistet haben.

Obwohl man, außer durch Zeitmessungen, sehr schlecht einsieht, daß shellsort gute Ergebnisse liefert, tatsächlich ist es bis heute noch nicht gelungen eine genaue mathematische Vorhersage über das Verhalten von shellsort zu gewinnen, ist von vorneherein klar, daß die Schrittweiten eine wichtige Rolle für die Güte des Sortierverfahrens darstellen. Zur Beendung der Sortierarbeit ist es zwar lediglich notwendig, daß der Sortieralgorithmus mit der Schrittweite k=1 abgeschloßen wird, die vorhergehenden Schritte tragen allerdings sehr zur Sortiergeschwindigkeit bei.

Ohne weitere Begründung (Die Mathematik läßt grüßen), gebe ich Ihnen deshalb zwei Schrittfunktionen an, die gute Ergebnisse liefern:

A: Die Folge ..., 121, 40, 13, 4, 1
B: Die Folge ..., 31, 15, 7, 3, 1

Wie Sie oben und im Listing 8e) gesehen haben, wurde von mir keine dieser Schrittfunktionen gewählt, da das ein Schrittweitenarray erfordern würde, was, in notwendiger Allgemeinheit, recht umständlich zu implementieren ist. Auch die von mir gewählte Schrittfunktion lieferte, wie im Folgenden ausgeführt, recht brauchbare Ergebnisse.

Abbildung 8e: Shellsort

      68 77 28 35 95 58 40 2 99 82 51 78 49 61 31
k=7 : 2 77 28 35 78 49 40 31 99 82 51 95 58 61 68
k=3 : 2 31 28 35 51 49 40 61 68 58 77 95 82 78 99
k=1 : 2 28 31 35 40 49 51 58 61 68 77 78 82 95 99

Testumgebung

Unsere heutige Testumgebung, Listing 8f), stellt uns drei mögliche Arten von Arrays zur Verfügung.

Zusätzlich können noch

Maßgeblich sind dabei natürlich die zufällig erzeugten Arrays. Die Zeitwerte für die anderen Arrays werden lediglich benötigt um das Verhalten der Algorithmen in Ausnahmesituationen (teil-, oder ganzsortierte Arrays) zu verdeutlichen.

Um beim nächsten Mal nicht noch eine zusätzliche Testumgebung stricken zu müssen, sind auch schon die Sortieralgorithmen der nächsten Folge in teste_sort aufgenommen worden. Zum reinen Test unserer heutigen Routinen wird es deshalb notwendig, daß Sie die Zeilen 17, 28-31, 104-107 und 116-119 ignorieren, sofern Sie sie nicht als Vorausschau auf Kommendes betrachten wollen.

Die Zeitmessung bereitete einige Schwierigkeit, da wir mit der Systemuhr nur in Zwei-Sekunden-Intervallen messen können. Heute ist dies noch nicht so problematisch, weil unsere Algorithmen, Ausnahme shellsort, noch recht schlecht sind, sich also lange Zeiten bereits bei einigen hundert Elementen ergeben können.

Doch 'Lange Rede kurzer Sinn'. Jetzt wirds praktisch.

Zeitmessung

Beginnen wir unsere Testreihe mit 500 Elementen und verdoppeln die Anzahl bis hin zu 8000 Elementen. Es ergeben sich für die fünf Sortieralgorithmen, mit den drei möglichen Formen von Arrays (aufsteigend/ random/ absteigend), die Werte der Abbildung 8f).

Von eigentlichem Interesse, sind dabei nur die Werte für die zufällig erzeugten Arrays, die wir nun etwas genauer betrachten wollen.

Beobachten können wir dabei zunächst das shellsort, sowieso schon weit und breit schnellster Algorithmus, mit wachsender Elementanzahl, immer besser abschneidet und die anderen Verfahren, angeführt von den beiden bubblesort Variationen, immer unakzeptablere Werte liefern.

Eine weitere Beobachtung ist die Art der Zeitentwicklung in Abhängigkeit von der Arraylänge. Verdoppelt man die Arraylänge, so ist bei allen Algorithmen, Ausnahme wiederum Shellsort, eine ungefähre Vervierfachung der Sortierzeiten ablesbar.

Es besteht also bei den vier Algorithmen eine quadratische Abhängigkeit, der Sortierzeit von der Anzahl der Elemente. Diese Eigenschaft kann man durch die Formel:

 zeit=Konstante * Elemente2

charakterisieren. In diesem Fall spricht man von einem Algorithmus der Ordnung O(n2). Allgemein spricht man, wenn eine Begebenheit der Art

 zeit=Konstante * Term

vorliegt, von einem Algorithmus der Ordnung O(Term).

Die quadratische Ordnung können Sie in der Abbildung 8g) auch sehr gut ablesen. Links dargestellt ist eine Ausgleichskurve durch unsere abgelesenen Werte, die, wie könnte es anders sein, Parabelform hat. Um die ganze Sache noch zu überprüfen, kann man noch die zweiten Wurzeln aus den Sortierzeiten ziehen (rechter Abbildungsteil). Es müssen sich dann Geraden ergeben. Hier passen auch erstmals die sehr kurzen Sortierwerte von shellsort größenordnungsmäßig ins Bild. Dummerweise ergibt sich, was man trotz der sehr kurzen Zeiten gut erkennen kann, keine Gerade, sondern eine leicht abgeflachte Kurve. Dies liegt daran, daß shellsort, bei geeigneter Schrittweitenfolge, eine Ordnung unterhalb von O(n2), unbewiesenerweise etwa in der Nähe von O(n1.2) besitzt.

Abbildung 8f: Sortierzeitmessungen (in Sekunden)

Anzahl   Array      Einfuegen  Auswahl  Bubblesort 1  Bubblesort 2  Shellsort
_____________________________________________________________________________
         --->       -          3.2      3.6           -             -
500 *)   Random     2.4        3.2      5.6           6.0           -
         <---       2.0        4.0      5.6           6.0           -
         --->       -          12       14            -             -
1000     Random     10         12       22            24            -
         <---       18         14       32            32            -
         --->       -          50       52            -             2
2000     Random     42         52       92            92            2
         <---       80         56       124           128           2
         --->       -          210      214           -             2
4000     Random     168        210      370           378           6
         <---       330        224      522           538           4
         --->       -          840      856           -             4
8000     Random     666        840      1478          1512          14
         <---       1316       898      2088          2156          6

*) : Mittelung von 5 Messungen
---> : Aufsteigend sortierter Array
Random : Zufallsarray mit Long_Integer-Werten von 0-1000000
<--- : Absteigend sortierter Array

Vorausschau

In der nächsten Folge werden wir uns mit Sortieralgorithmen der Ordnung O(n*log(n)) befassen, deren günstigste Vertreter in der Praxis noch einmal eine ganze Ecke (Faktor 2-4) schneller als shellsort sind. Einige wohlklingende Namen, in diesem Zusammenhang, sind heapsort und quicksort. Um eine iterative Variante von quicksort angeben zu können, werde ich zusätzlich darauf eingehen, wie man mit einem uns aus der ersten Folge wohlbekannten Hilfsmittel, den Stacks, wichtige rekursive Operationen iterativ darstellen kann.

Listings zu diesem Artikel


Dirk Brockhaus
Aus: ST-Computer 07 / 1988, Seite 75

Links

Copyright-Bestimmungen: siehe Über diese Seite