Algorithmen

Algorithmus ist hier besonders wichtig, da die Lese- und Schreibzugriffe auf externe Medien einen hohen Zeitbedarf beanspruchen. Ein Sortieralgorithmus wird als stabil bezeichnet, wenn er die relative Reihenfolge von Elementen beibehält, die den gleichen Wert bezüglich des Sortierschlüssels aufweisen. Ein Beispiel: Es liegt eine Schülerliste mit Namen und Noten vor, die alphabetisch sortiert ist. Diese soll nach Noten sortiert werden. Ein stabiler Algorithmus gewährleistet, dass nach dem Sortiervorgang Schüler mit den gleichen Noten weiterhin alphabetisch sortiert sind.
    Es existiert eine Menge von Algorithmen zur Sortierung von Datenbeständen. Diese alle hier vorzustellen, würde den zur Verfügung stehenden Rahmen sprengen und auch wenig sinnvoll sein. Auch existieren Varianten der Algorithmen. Im Einzelfall muss man also nachlesen! Tabelle 2 beschreibt einige bekannte Verfahren näher.
Name des Verfahrens
Beschreibung
Beispiel
Insertion Sort
Insertion Sort ist ein einfaches und stabiles Verfahren. Die Arbeitsweise ist effizient bei einem kleinen Datenumfang oder wenn eine Vorsortierung der Elemente vorliegt. Das Verfahren ist mit der natürlichen Vorgehensweise beim Sortieren von Spielkarten vergleichbar: Am Anfang liegen alle Karten auf dem Tisch. Nacheinander wird eine Karte aufgenommen und an der korrekten Position im Kartenblatt in der Hand eingeordnet. Um die richtige Einfügestelle zu finden (hier bei einer aufsteigenden Sortierung), wird jedes Element von links nach rechts durchlaufen und mit dem einzufügenden Element verglichen.
Abbildung 2
    Listing 2 (C#)
    Listing 3 (Delphi)
Bubble Sort
Beim Bubble-Sort-Algorithmus wird das Array durchlaufen und benachbarte Elemente werden miteinander verglichen und wenn nötig vertauscht. Der Algorithmus hat diesen Namen, da das Maximum wie eine Luftblase aufsteigt (bzw. von links nach rechts wandert). Der Bubble-Sort-Algorithmus gehört zur Klasse der so genannten In-place-Verfahren, d. h. für die Sortierung wird kein weiterer Speicher (zum Beispiel ein zweites Array) benötigt. Lediglich ein temporärer Datenspeicher für das Vertauschen von benachbarten Elementen ist von Nöten. Die Effizienz des Algorithmus ist als eher mangelhaft einzustufen, daher wird dieser in der Praxis nicht allzu häufig eingesetzt.
Abbildung 3
Shell Short
Der Shell-Sort-Algorithmus ist eine Erweiterung des Insertion-Sort-Verfahrens. Bei einer großen Zahl von Elementen ist Insertion Sort nicht sehr schnell, da es unter Umständen notwendig ist, viele Vergleiche durchzuführen, um die richtige Einfügeposition zu finden. Shell Sort versucht diesen Nachteil zu umgehen, indem die Sortierung schrittweise (im Sinne einer Vorsortierung) stattfindet.
Abbildung 4
Quick Sort
Quick Sort funktioniert nach dem Prinzip „Teile und herrsche“ und arbeitet rekursiv. Auf diesen Algorithmus wird in der Praxis häufig zurückgegriffen. Die Implementierung ist nicht schwierig und lässt sich auf viele Problemstellungen anwenden. Zu beachten ist, dass Quick Sort nicht stabil ist. Die prinzipielle Vorgehensweise ist wie folgt: Die Folge der zu sortierenden Daten wird in zwei Teilfolgen zerlegt. Danach werden beide Abschnitte unabhängig voneinander sortiert. Die Sortierung der Teilfolgen erfolgt wieder nach dem gleichen Prinzip der Zerlegung. Die rekursive Vorgehensweise wird fortgesetzt, bis nur noch ein Element in der Teilfolge existiert. Das Trennelement wird auch als Pivotelement bezeichnet und sollte für eine effiziente Arbeitsweise des Algorithmus idealerweise in der Mitte der Folge (bezüglich des Wertebereiches) liegen. Die Auswahl des Pivotelementes ist nicht ganz trivial, dazu existieren mehrere Ansätze (vgl. entsprechende Literatur). Nach der Teilung erfolgt die Zuordnung der Elemente. Dabei entsteht Folgendes:
Alle Elemente links vom Trennelement sollen kleiner oder gleich dem Trennelement sein.
Alle Elemente rechts vom Trennelement sollen größer oder gleich diesem sein.
    Das Trennelement erhält automatisch die richtige Position. Im nächsten Schritt wird der Algorithmus auf die beiden Teile angewendet. Der Vorgang ist abgeschlossen, bis jede Teilfolge nur noch ein Element enthält.
Abbildung 5
    Tabelle 2: Überblick über bekannte Sortierverfahren

    Abbildung 2: Die Arbeitsweise von Insertion Sort, vgl. [4]

    Abbildung 3: Beim Bubble Sort wird das größte Element vom Anfang zum Ende durchgereicht [4]

    Abbildung 4: Beim Shell Sort wird das Problem in Teilprobleme zerlegt