Dipl. Phys.  Gerald  Kempfer
Gastdozent an der Berliner Hochschule für Technik

Das Motto "Ordnung ist das halbe Leben" hat, wenn nicht im Leben, zumindest beim Programmieren seine Berechtigung. Sortieren von Datensätzen nach verschiedenen Kriterien oder zum Ordnen von Tabellen oder für schnellen Zugriff über binäres Suchen gehören zum tüglichen Brot.

Zwar werden von den meisten C-Compilern Standard-Algorithmen in Form von Bibliotheks-Funktionen mitgeliefert (zum Beispiel "QuickSort"); dennoch ist es wichtig, einen groben Überblick über die Problematik des Sortierens zu haben, damit die Leistungsfähigkeit der verschiedenen Verfahren beurteilt werden kann.

Zudem gehören Sortierverfahren neben Suchverfahren mit zu den am besten und ausführlichsten untersuchten Algorithmen in der Informatik.

Bei Sortierverfahren unterscheidet man zunächst "interne" und "externe" Verfahren. Bei internen Verfahren kann die gesamte zu sortierende Datenmenge im Arbeitsspeicher des Rechners gehalten werden (Sortieren von Arrays). Damit ist die maximale Anzahl der zu sortierenden Elemente beschränkt. Externe Verfahren (Bandsortierverfahren) unterliegen dieser Beschränkung nicht. Die Daten werden in sequentiellen Dateien abgelegt und durch Mischen dieser Dateien und einiger während des Sortierens anzulegender Hilfsdateien sortiert. Auf die externen Verfahren wird hier nicht weiter eingegangen.

In diesem Kapitel werden einige interne Sortierverfahren vorgestellt, die außerdem noch die Eigenschaft haben, dass außer dem Daten-Array kein weiterer Speicherplatz benötigt wird. Zur besseren Übersicht werden die hier vorgestellten Sortierverfahren nach der jeweils zugrunde liegenden Idee und nach ihrer Komplexität (siehe voriges Kapitel) eingeteilt:

Bei jedem Algorithmus ist die Komplexität des Verfahrens angegeben (zum Beispiel O(n)). Die Komplexität ist ein Maß dafür, wie die Laufzeit eines Programmes von der Größe des zu lösenden Problems abhängt.

Im Falle der Sortierverfahren bedeutet dies, dass zum Beispiel die Laufzeit von Bubble-Sort ungefähr quadratisch mit der Anzahl der zu sortierenden Elemente zunimmt. Eine gute Grundlage für die Bestimmung der Komplexität von Sortier-Algorithmen sind die Anzahl der notwendigen Vergleiche und Vertauschungen von Elementen – die beiden wesentlichen Operationen beim Sortieren.

In realen Anwendungen werden die höheren Verfahren Heap-Sort und vor allem Quick-Sort eingesetzt. Bei detaillierten Untersuchen hat sich die Überlegenheit von Quick-Sort über alle anderen hier vorgestellten Algorithmen herausgestellt. Quick-Sort schlägt Heap-Sort in der Geschwindigkeit noch um einen Faktor 2 bis 3.

Am schlechtesten schneidet fast immer Bubble-Sort ab. Allerdings benötigen Heap- und Quick-Sort eine gewisse Mindestgröße des zu sortierenden Arrays zum Ausspielen ihrer Leistungsfähigkeit. Bei sehr kleinen Arrays ist es dagegen z.B. sinnvoll, Sortieren durch direktes Auswählen einzusetzen.

Dieser Methode liegt folgende Idee zugrunde: Das zu sortierende Array wird gedanklich in einen linken und rechten Teil getrennt. Der linke Teil ist eine bereits sortierte Sequenz, in die die Elemente des rechten Teils nacheinander einsortiert werden müssen.

Zu Beginn des Sortiervorgangs besteht der bereits sortierte linke Teil nur aus dem ersten Element des Arrays (jedes Element stellt für sich allein eine sortierte Sequenz der Länge eins dar). Alle anderen Elemente gehören zum unsortierten rechten Teil.

Solange nun der rechte Teil nicht leer ist, wird das jeweils erste Element des rechten Teils in die sortierte Sequenz eingefügt. Einfügen heißt dabei, das Element solange mit seinem linken Nachbarn zu vertauschen, bis dieser entweder kleiner ist oder der linke Rand des Arrays erreicht wird (dieses Element ist dann das kleinste bisher gefundene).

Das folgende Beispiel soll dieses Verfahren verdeutlichen. Dabei gibt der senkrechte Strich die Trennung zwischen sortierten und unsortierten Teil an.

Beispiel:

Die dazugehörige Sortierfunktion für ein zu sortierendes Zahlen-Array sieht wie folgt aus.

kap09_01.c

01 /***********************************************************
02  * Sortieren durch direktes Einf gen
03  * Sortiert das angegebene Zahlen-Array in aufsteigender
04  * Reihenfolge.
05  * Parameter: Array – Zeiger auf das zu sortierende Array
06  * Anzahl – Anzahl der Elemente im Array
07  * Rückgabe: nichts
08  ***********************************************************/
09 void InsertSort(int *Array, int Anzahl)
10 {
11    int i;       /* erstes Element im unsortierten Teil   */
12    int j;       /* Laufindex zum Einsortieren            */
13    int temp;    /* für Austausch zweier Elemente         */
14
15    for (i = 1; i < Anzahl; i++)
16    {
17       j = i;
18       while (j > 0 && *(Array + j) < *(Array + j – 1))
19       {
20          /* Element an der Stelle j mit linkem Nachbarn tauschen */
21          temp = *(Array + j);
22          *(Array + j) = *(Array + j – 1);
23          *(Array + j – 1) = temp;
24          j--;
25       }
26    }
27 }

Auch bei dieser Methode unterscheidet man einen sortierten und unsortierten Teil des Arrays. Die bereits sortierte Sequenz wird beim direkten Auswählen dadurch vergr&oouml;ßert, dass man das kleinste Element des noch unsortierten Teils auswählt und mit einer einzigen Vertauschoperation in die sortierte Sequenz einfügt.

Beispiel:

Der Vorteil von Sortieren durch Auswählen gegen¨ber Sortieren durch Einfügen liegt darin, dass pro Element zwar mehrere Vergleiche jedoch nur eine Vertauschung stattfindet. Dies spielt vor allem eine Rolle, wenn nicht ganze Zahlen sondern große Datensätze wie Adressen sortiert werden, da dann im allgemeinen die Vergleichsoperation schneller als das Vertauschen ist.

Hier die dazugehörige Funktion:

kap09_02.c

01 /***********************************************************
02  * Sortieren durch direktes Auswaehlen
03  * Sortiert das angegebene Zahlen-Array in aufsteigender
04  * Reihenfolge.
05  * Parameter: Array  – Zeiger auf das zu sortierende Array
06  *            Anzahl – Anzahl der Elemente im Array
07  * Rueckgabe: nichts
08  ***********************************************************/
09 void SelectSort(int *Array, int Anzahl)
10 {
11    int i;      /* erstes Element im unsortierten Teil */
12    int j;      /* Laufindex zum Suchen                */
13    int min;    /* kleinstes gefundenes Element        */
14    int temp;   /* fuer Austausch zweier Elemente      */
15
16    for (i = 0; i < Anzahl – 1; i++)
17    {
18       min = i;
19       for (j = i + 1; j < Anzahl; j++)
20       {
21          /* suche kleinstes Element */
22          if (*(Array + j) < *(Array + min))
23             min = j;
24       }
25       temp = *(Array + min);
26       *(Array + min) = *(Array + i);
27       *(Array + i) = temp;
28    }
29 }

Das zu sortierende Array wird mehrmals von rechts nach links durchlaufen und das jeweilige Element mit seinem linken Nachbarn vertauscht, falls die beiden nicht in der richtigen Reihenfolge stehen. Die kleineren Elemente wandern also von rechts nach links. Stellt man sich das Feld senkrecht und die kleineren Elemente als 'leichtere' Blasen ('bubbles') vor, die im Feld in eine ihrem Gewicht entsprechende Stelle aufsteigen, so findet man die Erklärung für den Namen Bubble-Sort.

Beispiel:

Für Bubble-Sort gibt es verschiedene Varianten. Sie unterscheiden sich im wesentlichen im Laufbereich der Indizes. Hier die erste Variante:

kap09_03.c

01 /***********************************************************
02  * Bubble-Sort Variante 1
03  * Sortiert das angegebene Zahlen-Array in aufsteigender
04  * Reihenfolge.
05  * Parameter: Array  – Zeiger auf das zu sortierende Array
06  *            Anzahl – Anzahl der Elemente im Array
07  * Rueckgabe: nichts
08  ***********************************************************/
09 void BubbleSort1(int *Array, int Anzahl)
10 {
11    int i;      /* erstes Element im unsortierten Teil */
12    int j;      /* Index der aufsteigenden Blasen      */
13    int temp;   /* fuer Austausch zweier Elemente      */
14
15    for (i = 1; i < Anzahl; i++)
16       for (j = Anzahl - 1; j >= i; j--)
17          if (*(Array + j) < *(Array + j - 1))
18          {
19             temp = *(Array + j);
20             *(Array + j) = *(Array + j - 1);
21             *(Array + j - 1) = temp;
22          }
23 }

Und hier die zweite Variante:

kap09_04.c

01 /***********************************************************
02  * Bubble-Sort Variante 2
03  * Sortiert das angegebene Zahlen-Array in aufsteigender
04  * Reihenfolge.
05  * Parameter: Array  – Zeiger auf das zu sortierende Array
06  *            Anzahl – Anzahl der Elemente im Array
07  * Rueckgabe: nichts
08  ***********************************************************/
09 void BubbleSort2(int *Array, int Anzahl)
10 {
11    int i;      /* erstes Element im unsortierten Teil */
12    int j;      /* Index der aufsteigenden Blasen      */
13    int temp;   /* fuer Austausch zweier Elemente      */
14
15    for (i = 0; i < Anzahl - 1; i++)
16       for (j = i + 1; j < Anzahl; j++)
17          if (*(Array + j) < *(Array + i))
18          {
19             temp = *(Array + i);
20             *(Array + i) = *(Array + j);
21             *(Array + j) = temp;
22          }
23 }

Shell-Sort ist eine Verfeinerung des Sortierens durch direktes Einfügen. Eine Effizienzsteigerung lässt sich beim Sortieren dadurch erreichen, dass Elemente in verkehrter Reihenfolge vorzugsweise über größere Distanzen ausgetauscht werden. Dieses nutzt Shell-Sort aus, indem zunächst alle Sequenzen von Elementen, die vier Positionen entfernt liegen, sortiert werden (4-Sortierung). Danach werden alle Elemente mit Abstand 2 (2-Sortierung) und zuletzt die Elemente mit Abstand 1 (1-Sortierung) sortiert.

Beispiel:

Innerhalb der einzelnen k-Sortierungen wird durch "Sortieren durch direktes Einfügen" sortiert. Der Vorteil des Verfahrens liegt nun darin, dass entweder nur wenige Elemente sortiert werden müssen oder die Elemente bereits teilweise vorsortiert sind, so dass nur wenige Umstellungen notwendig sind.

Die Folge der Schrittweiten für die k-Sortierungen kann beliebig gewählt werden, sofern die letzte Schrittweite 1 ist. Im schlechtesten Fall verrichtet der Durchlauf mit Schrittweite 1 die ganze Arbeit. Eine gute Folge von Schrittweiten ist:

   s(i) = 1, 3, 7, 15, 31, ...
   mit s(i) = 2 * s(i – 1) + 1     und     s(1) = 1.

Für diese Folge ergibt die mathematische Analyse des Algorithmus einen zu n^1.2 proportionalen Aufwand.

Hier die Funktion für Shell-Sort:

kap09_05.c

01 /***********************************************************
02  * Shell-Sort
03  * Sortiert das angegebene Zahlen-Array in aufsteigender
04  * Reihenfolge.
05  * Parameter: Array  – Zeiger auf das zu sortierende Array
06  *            Anzahl – Anzahl der Elemente im Array
07  * Rueckgabe: nichts
08  ***********************************************************/
09 #define STEPS 5
10 void ShellSort1(int *Array, int Anzahl)
11 {
12    static steps[STEPS] = {1, 3, 7, 15, 31}; /* Schrittweiten     */
13    int idx;    /* Index der aktuellen Schrittweite               */
14    int i;      /* Index des naechsten einzusortierenden Elements */
15    int j;      /* Laufindex zum Einsortieren                     */
16    int temp;   /* fuer Austausch zweier Elemente                 */
17
18   for (idx = STEPS - 1; idx >= 0; idx--)
19       /* fuer alle Schrittweiten */
20       for (i = steps[idx]; i < Anzahl; i++)
21       {
22          j = i;
23          /* Einsortieren durch direktes Einfuegen */
24          while (j > 0 && *(Array + j) < *(Array + j – steps[idx]))
25          {
26             temp = *(Array + j);
27             *(Array + j) = *(Array + j – steps[idx]);
28             *(Array + j - steps[idx]) = temp;
29             j -= steps[idx];
30          }
31       }
32 }
33 #undef STEPS

Quick-Sort wird seinem Namen wirklich gerecht. Es ist die schnellste der vorgestellten Sortiermethoden und daher eine der am häufigsten verwendeten. Der Schlüssel zu Quick-Sort liegt im wiederholten Aufspalten des Arrays in zwei, wenn möglich etwa gleich große Teile, die für sich getrennt weiter sortiert werden. Dies ist dann möglich, wenn die Elemente einer Hälfte alle kleiner gleich den Elementen des anderen Teils sind.

Man muss also dafür sorgen, dass alle Elemente, die kleiner oder gleich einer bestimmten Schranke sind, in den linken Teil und alle Elemente größer gleich der Schranke in den rechten Teil des Arrays wandern. Dies wird durch die Funktion partition erreicht.

Nach dem Aufteilen des Arrays wird auf beide Teile das gleiche Verfahren wieder angewendet. Dies geschieht durch den rekursiven Aufruf der Quick-Sort-Routine (siehe auch Kapitel Funktionen Abschnitt Rekursiver Funktionsaufruf im Skript Programmieren in C). Die Abbruchbedingung der Rekursion ist dann gegeben, wenn das zu sortierende Teil-Array leer ist oder nur noch aus einem einzigen Element besteht (was sollte dann noch sortiert werden?).

Die Problemgröße halbiert sich jeweils bei einer solchen Spaltung, woraus sich letztendlich auch die Effizienz des Verfahrens ergibt. Dabei muss man allerdings aufpassen, dass bei unglücklicher Wahl der Schranke nicht ein Teil leer bleibt, wenn z.B. alle Elemente kleiner bzw. größer als der Schranke sind.

Im einfachsten Fall wird das erste Element als Schranke gewählt und dieses nach dem Zerlegen des Arrays zwischen beide Teile gesetzt. Damit ist die Schranke selber bereits einsortiert und es müssen nur noch die beiden Teile vor und nach der Schranke sortiert werden.

Folgendes Beispiel zeigt die entstehenden Zerlegungen des Arrays: Wenn die einzelnen Partitionen am Ende wieder zusammengenommen werden, erhält man das sortierte Array. Dabei sind die Schranken immer fett und die bereits sortierten Teile unterstrichen gedruckt.

Beispiel:

Wichtig für die Effizienz von Quick-Sort ist eine gute Wahl der Schranke. Quick-Sort ist am effizientesten, wenn das Array bei jeder Zerlegung in gleich große Teile partitioniert wird. Im schlechtesten Fall (z.B. wenn das Array bereits sortiert ist) wird bei jeder Zerlegung nur ein Element – nämlich die Schranke selber – abgespalten. Dann ist die Schnelligkeit von Quick-Sort verloren. Als Schranke sollte daher der mittlere Wert der Elemente gewählt werden. Allerdings kennt man diesen aber erst, wenn das Array sortiert ist. Eine Möglichkeit ist es, drei Elemente aus dem Array herauszugreifen und den mittleren als Schranke zu verwenden. Im Fall des bereits sortierten Arrays wird die Leistung von Quick-Sort dadurch wesentlich verbessert.

Noch ein weiterer Punkt kann Probleme bereiten: Die rekursiven Aufrufe benötigen Speicherplatz für Funktionsparameter und Hilfsvariablen. Im oben geschilderten schlechtesten Fall entstehen n (n ist die Anzahl der Elemente) "hängende" rekursive Aufrufe, falls immer zuerst die größere der Partitionen weiter sortiert wird.

Außerdem kosten die ständigen Funktionsaufrufe Zeit. Dies kann mit einer iterativen Fassung (also Schleifen statt rekursive Funktionsaufrufe) vermieden werden.

Hier nun die Quick-Sort- und die dazugehörigen Funktionen:

kap09_06.c

01 /**********************************************************
02  * int partition(int *Array, int ui, int oi)
03  * Unterteilt das angegebene Array in zwei Teile, wobei
04  * im linken Teil alle Werte kleiner und im rechten Teil
05  * alle Werte groesser als die mittlere Schranke sind. Der
06  * Index der Schranke wird zurueckgegeben.
07  * Parameter: Array – das zu sortierende Array
08  *            ui    - der untere Index des Teils des
09  *                    Arrays, der sortiert werden soll
10  *            oi    - der obere Index (entsprechend ui)
11  * Rueckgabe: int   - Index der Schranke
12  **********************************************************/
13 int partition(int *Array, int ui, int oi)
14 {
15    int i = ui, j = oi;         /* Laufindizes                     */
16    int temp;                   /* fuer Austausch zweier Elemente  */
17    int *comp = Array + ui;     /* Vergleichselement (Schranke)    */
18
19    while (i <= j)
20    {
21       /* naechstes Element > comp von links suchen (im li. Teil)  */
22       while (i <= j && *(Array + i) <= *comp)
23          i++;
24       /* naechstes Element < comp von rechts suchen (im re. Teil) */
25       while (j >= i && *(Array + j) >= *comp)
26          j--;
27       if (i < j)
28       {
29          temp = *(Array + i);
30          *(Array + i) = *(Array + j);
31          *(Array + j) = temp;
32          i++;
33          j--;
34       }
35    }
36    i--;
37    /* setze Vergleichselement (Schranke) zwischen beide Teile     */
38    temp = *(Array + ui);
39    *(Array + ui) = *(Array + i);
40    *(Array + i) = temp;
41    return i;
42 }
43
44 /**********************************************************
45  * void qsort(int *Array, int ui, int oi)
46  * Unterteilt das Array in zwei Teile (Funktion
47  * partition) und ruft sich selber fuer beide Teile
48  * erneut auf.
49  * Parameter: Array – das zu sortierende Array
50  *            ui    - der untere Index des Teils des
51  *                    Arrays, der sortiert werden soll
52  *            oi    - der obere Index (entsprechend ui)
53  * Rueckgabe: keine
54  **********************************************************/
55 void qsort(int *Array, int ui, int oi)
56 {
57    int idx;                        /* Schranke einer Zerlegung        */
58
59    if (ui >= oi)                   /* Abbruchbedingung der Rekursion  */
60       return;
61    else
62    {
63       idx = partition(Array, ui, oi);
64       qsort(Array, ui, idx – 1);   /* linken Teil rekursiv sortieren  */
65       qsort(Array, idx + 1, oi);   /* rechten Teil rekursiv sortieren */
66    }
67 }
68
69 /***********************************************************
70  * Quick-Sort
71  * Sortiert das angegebene Zahlen-Array in aufsteigender
72  * Reihenfolge.
73  * Parameter: Array  – Zeiger auf das zu sortierende Array
74  *            Anzahl – Anzahl der Elemente im Array
75  * Rueckgabe: keine
76  ***********************************************************/
77 void QuickSort(int *Array, int Anzahl)
78 {
79    qsort(Array, 0, Anzahl – 1);
80 }

Voriges Kapitel: 8. Komplexität

Nächstes Kapitel: 10. Listen