Sortieralgorithmen - eine Einführung | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Überblick
|
EinleitungDas Sortieren ist eines der wichtigsten Gebiete der Datenverarbeitung. Circa 25% aller Rechenzeit im kommerziellen Bereich wird auf das Sortieren von Daten verwendent [6]. An Beispielen zum Sortieren mangelt es nicht:
Wie aber einer Rechenanlage beibringen, Daten zu sortieren? Natürlich durch einen Algorithmus. Im Streben, immer schnellere und effizientere Algorithmen zu entwickeln, sind heutzutage bereits viele Sortieralgorithmen bekannt. Einige von ihnen sollen in diesem Text vorgestellt werden. Zuerst stellt sich aber die Frage, was ist Sortieren eigentlich? Natürlich fehlt es hier auch nicht an einer Definition: "Unter Sortieren versteht man allgemein den Prozess des Anordnens einer gegebenen Menge von Objekten in einer bestimmten Ordnung." ([7], Kapitel 2, Seite 77) VereinbarungenIm folgenden werden gewisse Vereinbarungen getroffen:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
Sortieren durch MischenDer bekannteste und nebenbei auch einer der einfacheren Sortieralgorithmen ist BubbleSort. Allerdings ist es für große zu sortierende Mengen aufgrund seiner Geschwindigkeit eher ungeeignet. Warum das so ist, läßt sich leicht zeigen: Angenommen, das zu sortierende Array besteht aus n Elementen. Dann wird dieses Array auch (n-1)mal durchlaufen, wobei bei jedem Durchlauf verschieden viele Vergleiche durchgeführt werden. Abubble(n) sei die Anzahl der nötigen Vergleiche für n Elemente. Abubble(n) = 0,5 · (n*n - n) Beweis: Beim ersten Durchlauf wird das Array bis zum (n-1)ten Element durchlaufen (demzufolge finden (n-1) Vergleiche statt), beim zweiten bis zum (n-2)ten Element und beim letzten Durchlauf schließlich nur noch bis zum 1. Element (1 Vergleich) . Abubble(n) ist demzufolge: Abubble(n) = (n-1) + (n-2) + (n-3) + ... + (n-(n-1))
= 0,5·n·(n+1) - n
= 0,5·n*n + 0,5*n - n
= 0,5·n*n - 0,5·n
= 0,5·(n*n - n)
Bei hohen n explodiert die Zahl der nötigen Vergleiche geradezu. Wenn sich
n verdoppelt, vervielfacht sich die Anzahl der nötigen Vergleiche um mehr
als das vierfache. Das läßt sich aber auch umgekehrt sagen:
Halbiert man n, so viertelt man Abubble: Abubble(0,5·n) = 0,25·Abubble(n) Das kann man sich jetzt zunutze machen. Wenn man die n Elemente in zwei Teile teilt und sie getrennt sortiert, so braucht man nur halb soviel Zeit, als wenn man sie zusammen sortiert. Hier hätten wir also die Idee zu einem für uns neuen Sortieralgorithmus: Beschreibung: Wenn man n Elemente sortieren will, so teilt man das Feld, daß diese Elemente enthält, in der Mitte und sortiert beide Hälften getrennt voneinander. Anschließend besitzt man ein Feld, daß aus zwei Teilen besteht, welche beide sortiert sind. Das Feld an sich ist aber noch nicht sortiert. Also müssen wir zum Abschluß die beiden sortierten Hälften noch so miteinander mischen, daß das Feld vollkommen sortiert ist. Wie aber mischt man die beiden Hälften? Diese Frage soll weiter unten beantwortet werden. Zuerst wollen wir uns aber ein Beispiel ansehen: Nehmen wir an, wir haben ein Feld, welches aus den folgenden Zahlen, in dieser Reihenfolge, besteht: 5 8 2 6 1 9 7 3 Zuerst teilen wir das Feld also in zwei Hälften: 5 8 2 6 und 1 9 7 3 Anschließend sortieren wir beide Hälften, und zwar jede für sich. Das Ergebnis sieht dann folgendermaßen aus: 2 5 6 8 und 1 3 7 9 Wie man sieht, sind beide Hälften fein säuberlich in sich sortiert. Insgesamt gesehen ist das gesamte Feld aber noch nicht fertig sortiert, da die 1 ja schließlich vor die 2 muß. Deshalb müssen wir die beiden Hälften miteinander mischen: Um das zu tun, brauchen wir vier Zeiger:
Desweiteren brauchen wir zwei Läufer:
Am Anfang ist links:=start_links und rechts:=start_rechts. Um die zwei Hälften (start_links bis ende_links und start_rechts bis ende_rechts) zu sortieren, müssen wir nun folgendes machen: Vorbereitg.: Wir legen ein Hilfsfeld an, in das wir die beiden Hälften mischen.
Gegenüber BubbleSort ist dieser Sortieralgorithmus nun wie erwartet ungefähr doppelt so schnell. Jetzt aber nochmal das Mischverfahren am Beispiel: Von unserem letzten Beispiel haben wir noch folgendes Feld übrig (s.o.) :
2 5 6 8 1 3 7 9
sl el sr er
l r
Start_links (sl) zeigt auf die 2, das erste Element der linken Hälfte, start_rechts (sr) auf die 1, das erste Element der rechten Hälfte, ende_links (el) auf die 8 und ende_rechts (er) auf die 9 (jeweils das letzten Element der Seite). Die Läufer links (l) und rechts (r) zeigen auf die 2 und auf die 1. Wie oben in (1) beschrieben, vergleichen wir die Zahlen an der Position links und an der Position rechts. Das wäre also die 2 und die 1. Die 1 ist bewiesenermaßen kleiner als die 2, also schreiben wir die 1 in das Hilfsfeld und erhöhen rechts:
2 5 6 8 1 3 7 9
l r
Nun machen wir weiter, indem wir die Zahlen bei links und rechts wieder vergleichen. Diesmal ist die 2 kleiner als die 3, also kommt die 2 in das Hilfsfeld, hinter die 1, und links wird erhöht. Einige Durchläufe von (1) weiter, bietet sich uns das folgendes Bild:
2 5 6 8 1 3 7 9
l r
Hilfsfeld : 1 2 3 5 6 7
Zuletzt wurde die 8 mit der 7 verglichen. Die 7 wurde in das Hilfsfeld geschrieben und rechts wurde erhöht. Nun vergleichen wir die 8 mit der 9 und schreiben die 8 in das Hilfsfeld. Anschließend erhöhen wir links um 1. Wir haben jetzt unsere Abbruchbedingung erreicht ("l" hat die gesamte linke Hälfte einmal durchlaufen) und schreiben demzufolge die Zahlen, die in der rechten Hälfte übriggeblieben sind (von rechts bis ende_rechts) in das Hilfsfeld. Damit wäre die Mischung abgeschlossen. Das grobe Ablaufschema sieht jetzt ungefähr so aus:
Wir haben also die Anzahl der nötigen Vergleiche zum Sortieren eines Feldes halbiert, indem wir die Elemente aufteilten und getrennt sortierten. Eine Fortführung dieser Idee besteht darin, auf die Zuhilfenahme eines anderen Sortieralgorithmus' ganz zu verzichten, und statt dessen die beiden Hälften nochmal zu teilen und so weiter. Falls das so lange gemacht wird, bis die Teile nur noch ein Element groß sind, werden sie beim anschließendem Mischen in einer aufsteigenden Reihenfolge sortiert. Dieses Verfahren heißt Mergesort. Der Geschwindigkeitsvorteil, der dabei erzielt wird, ist gegenüber dem einmaligen Teilen - Sortieren - Mischen enorm. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
Weitere SortieralgorithmenNeben dem obengenannten Sortieralgorithmus gibt es noch weitere Algorithmen, namentlich Diese sechs (fünf ohne Mischsort, das ja bereits ausführlich beschrieben wurde) Algorithmen sollen in diesem Kapitel ganz kurz vorgestellt und erläutert werden. Dabei wird auf eine detaillierte Beschreibung (sowie einem Struktogramm) verzichtet. Im Anhang befindet sich ein Programm, welches sämtliche Sortieralgorithmen, die hier vorgestellt werden, als Prozeduren beinhaltet. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
Bubble-SortHeißt übersetzt etwa soviel wie Blasensortieren, was dadurch kommt, daß während des Sortierens die großen Werte wie Blasen aufsteigen. Ansonsten gehört es, wie auch RippleSort, zum "Sortieren durch Austauschen". Das Aufsteigen der großen Werte wird dadurch erreicht, daß die Elemente von vorne bis zum Ende durchlaufen werden und das aktuelle Element mit dem nachfolgenden vertauscht wird, sollte letzteres kleiner sein. Im Anschluß befindet sich die größte Zahl des Feldes am Ende. Diese Aktion wird wiederholt (allerdings nicht mehr bis zum Ende, sondern nur noch bis dahin, wo die sortierten großen Werte sind) bis das gesamte Array sortiert ist, oder das Array einmal durchlaufen wurde, ohne das ein Tausch stattfand. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
Ripple-SortRipple-Sort ist eine Art Bubble-Sort, allerdings wandern hier die kleinen Zahlen nach vorne (daher auch der Name: kleine Welle). Der Algorithmus durchläuft das Array von 1 bis n-1. An jeder Stelle kontrolliert er, ob ein noch kleineres Element folgt. Ist dem so, wird dieses Element mit dem Element, wo RippleSort gerade "steht", vertauscht. Folgt nach dem kleineren Element ein noch kleineres Element, wird wieder getauscht, ansonsten wird zum nächsten Element gegangen. RippleSort sehr ähnlich ist Selection-Sort. Der grundlegende Ablauf ist derselbe, allerdings wird gezielt nach dem kleinsten Element gesucht, und dann erst vertauscht. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
MinimumSucheDie Minimumsuche ist einer der einfachsten Sortieralgorithmen. Das Verfahren ist ganz einfach: Es wird ein Hilfsfeld angelegt, das genauso groß wie das originale Array ist. Anschließend wird das Originalarray n-mal vollständig durchlaufen. Bei jedem Durchlauf wird nach dem kleinsten Element Ausschau gehalten, das dann in das Hilfsfeld geschrieben wird. Damit dieser Wert beim nächsten Durchlauf nicht nochmal gefunden werden kann, wird er mit dem größtmöglichsten Wert überschrieben. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
Insertion-SortInsertion-Sort (Sortieren durch Einfügen) ist ein Algorithmus, der genauso arbeitet, wie man selbst Daten, z.B. Karten, sortieren würde. Es durchläuft nämlich das Array von vorne bis hinten und sucht bei jeder Stelle das nachfolgende kleinste Element. Wenn ein kleineres existiert, werden die Werte vom aktuellen Element bis zum kleinsten Element um eins nach hinten verschoben, und das kleinste Element wird davor eingefügt. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
QuickSortQuickSort ist, wie der Name schon sagt, der schnellste gebräuchliche Sortieralgorithmus. Er funktioniert nach dem Prinzip Teile-und-Herrsche. Aus der Mitte des aktuellen Feldbereiches (zu Beginn das gesamte Feld), wird eine Testzahl herausgepickt. Anschließend werden alle anderen Zahlen, je nach Größe durch Vertauschen vor oder hinter die Mitte eingeordnet. Anschließend ruft sich QuickSort selbst auf (rekursiv) um die beiden Hälften nach eben beschriebenem Verfahren zu sortieren ... Die Abbruchsbedingung ist erreicht, wenn der Feldbereich nur noch ein Element groß ist. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
Weitere SortieralgorithmenNeben den eben vorgestellten Algorithmen gibt es natürlich noch weitere, z.B.:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
GeschwindigkeitsvergleicheWie man sich denken kann, sind alle Algorithmen unterschiedlich schnell. Im folgenden werden verschiedene Tabellen aufgelistet, die die Zeit angeben, welche die Algorithmen für ein bestimmtes n braucht. Alle Messungen wurden unter folgenden Bedingungen durchgeführt:
(Die Zahl in der letzten Spalte benennt die Anzahl der Elemente. Die Spalten "sortiert", "zufällig" und "invers sortiert" enthalten die Werte, die der jeweilige Algorithmus gebraucht hat, um solch ein Feld zu sortieren. Sämtliche Zeitangaben sind in Sekunden. Zu den Zeiten muß aber noch gesagt werden, daß sie vom "wahren" Wert um bis zu einer Sekunde abweichen können. Das liegt daran, daß die Werte vom Computerprogramm selbst gemessen wurden und der Ablauf des Programms durch im Hintergrund laufende Programme verlangsamt worden sein könnte. Alle Meßreihen wurden aber unter gleichen Bedingungen durchgeführt und bei einigen Werten wurde von mehreren Meßversuchen der Mittelwert genommen. Ansonsten sollte sich eine eventuelle negative Beeinflussung größtenteil ausgleichen. Desweiteren sind ein Großteil der Algorithmen im Rahmen der Aufgabenstellung nicht optimiert.) Beim Ansehen der Tabelle merkt man sofort den gewaltigen Vorsprung, den QuickSort (aus diesem Grund auch von seinem "Erfinder" C. A. R. Hoare so benannt) besitzt. Alle anderen Algorithmen sind für etwas größere n drastisch langsamer. Trotzdem ist der Gebrauch von QuickSort nicht in allen Anwendungsfällen vorzuziehen. Für wenige Zahlenwerte reicht BubbleSort oder ein ähnlich einfacher Algorithmus vollkommen aus. Der Zeitunterschied fällt dann gar nicht ins Gewicht. Das ist übrigens typisch für komplexere Sortieralgorithmen. Der erhöhte Aufwand zahlt sich meist erst bei höheren n richtig aus. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
Auswertung
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
Kriterien für die Auswahl von SortieralgorithmenEin Aspekt, der immer bei der Wahl von Sortieralgorithmen beachtet werden sollte (und muß), ist die Art der Speicherung der Werte. Da wäre zum einen die Möglichkeit, daß die Daten im Hauptspeicher (RAM) in Form eines Arrays liegen, andererseits könnten sie auch in einer Datei auf einem Festspeicher (z.B. Diskette) sein. Bei kleinen n wäre es möglich, daß die Daten aus der Datei in den Speicher geladen und dort sortiert werden. Bei großen n macht sich das allerdings schlecht, da es dann leicht zu Speicherproblemen kommen kann. Man muß in dem Fall also einen Sortieralgorithmus benutzen, der sequentiell auf Daten zugreift. Das sind in der Regel Algorithmen, die das Prinzip des Mischens verwenden. Aber auch im ersten Fall (Daten im Hauptspeicher) ist nicht jeder Algorithmus günstig (mal ganz abgesehen von Geschwindigkeitsunterschieden). Einige Verfahren, namentlich die Minimumsuche, legen nämlich ein zweites Array an, das manchmal genauso groß wie das originale Feld ist. Das das bei vielen Zahlen- oder sonstigen Werten sehr ungünstig sein kann, sei mit dem Hinweis auf den oft begrenzten Hauptspeicher bewiesen. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Zum Anfang |
AnhangQuellenangaben
[1] Owsnicki-Klewe, Bernd
Algorithmen und Datenstrukturen
(Inf & Ing; Bd. 5)
Dr. Bernd Wißner, Augsburg
1. Auflage, 1994
[2] Mehlhorn, Kurt
Datenstrukturen und effiziente Algorithmen
Band 1: Sortieren und Suchen
Teuber, Stuttgart
1986
[3] Oestereich, Bernd
Algorithmen - Sortieren
aus: c't, Seite 273-276
Heft 11, 1988
[4] Dipl.-Ing. (FH) Schültz, Helbring
Das "Bubble-Sort-Verfahren"
(Ein Sortieralgorithmus unter der Lupe)
aus: Elektronik, Seite 72-81
Heft 11, Jahrgang 39, 25.05.1990
[5] Sortieralgorithmen in Pascal: "Ordnung muß sein"
aus: Dos international, Seite 254-258
Heft 12, Jahrgang 8, 1994
[6] Ottmann, Thomas
Algorithmen und Datenstrukturen
Bibliographisches Institut & F.A. Brockhaus AG
2. Auflage, 1993
[7] Wirth, Niklaus
Algorithmen und Datenstrukturen
B.H. Teubner, Stuttgart
4. Auflage, 1995
[8] Sedgewick, Robert
Algorithmen
Addison-Wesley
1. Auflage, 1991
[1], [6], [7] und [8] besitzen jeweils ein oder mehr Kapitel, die sich mit dem Sortieren von Daten beschäftigen. Desweiteren kann verwiesen werden auf: c't : Heft 3 und 4, 1992 |