Sortieralgorithmen

Sortiervorgänge kommen in der Praxis oft vor. Viele Softwarewerkzeuge bieten eine Sortierfunktion an, die auf intelligenten Sortieralgorithmen beruht. Selber Nachdenken oder eine Recherche zu dem Thema zeigen, dass es eine Vielzahl an Möglichkeiten gibt, Sortiervorgänge systematisch zu konzipieren. …

Das Sortierproblem besteht darin, Verfahren zu entwickeln, die eine sortierte Anordnung von Datenbeständen automatisiert erzeugen.

Dabei spielt es keine entscheidende Rolle, wie kompliziert die Datenobjekte des Datenbestandes sind. Wir können uns bei der Entwicklung von Sortierverfahren erst einmal auf ganz einfache Datenbestände fokussieren. Ein ganz einfacher Datenbestand sind Zahlen. Im Folgenden betrachten wir die Situation, dass eine Liste von Zahlen gegeben ist. Ziel ist es, diese Zahlen aufsteigend der Größe nach anzuordnen.

Zur Lösung des Sortierproblems sind eine Vielzahl an Verfahren entwickelt worden. Wir werden einige dieser Verfahren hier vorstellen. Um die Grundideen möglichst einfach zu gestalten, sollen nur Zahlen anstelle komplexer Datensätze betrachtet werden.

• Selectionsort
• Insertionsort
• Bubblesort
• Quicksort

Ziel der folgenden Untersuchungen ist es, das Laufzeitverhalten von Sortieralgorithmen systematisch zu ermitteln und die Ergebnisse genauer zu analysieren.

Hierzu bestimmen wir die Laufzeit t(n) in Abhängigkeit der Listenlänge n für wachsende Listenlängen (z.B. n = 1000, 2000, …).

Die zu sortierenden Listen werden mit Zufallszahlen gefüllt. Bei der Erzeugung der Testlisten wird der Zahlenbereich, aus dem die Zufallszahlen stammen, an die Listengröße angepasst, um ähnliche Ausgangssituationen zu erhalten.

Fallanalysen Die Anzahl der Vergleiche bei der Ausführung eines Sortieralgorithmus hängt manchmal nicht nur von der Problemgröße n (d.h. der Anzahl der Listenelemente) ab, entscheidend ist auch, wie stark die Liste bereits vorsortiert ist.

Bei einer Kostenanalyse unterscheidet man daher oft die folgenden Fälle:

• best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus der geringste Aufwand erforderlich ist
• worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus der meiste Aufwand erforderlich is
• average case (durchschnittlicher Fall): eine Mittelung über alle Fälle

Für die Praxis am wichtigsten ist meist der durchschnittliche Fall. Dieser ist aber schwer zu ermitteln. Wir konzentrieren uns hier daher auf den besten und schlechtesten Fall, wobei letzterer meist der relevantere ist.

Hier muss man in jedem Fall im ersten Schritt n-1 Vergleiche durchführen, im zweiten Schritt n-2 Vergleiche usw.. Es gilt also:

T_best(n) = (n-1) + (n-2) + … + 1

T_worst(n) = (n-1) + (n-2) + … + 1

Im ungünstigsten Fall muss beim Einfügen der gesamte bereits vorliegende sortierte Teil durchlaufen werden. Hier gilt dann:

T_worst(n) = 1 + 2 + … + (n-1)

Im günstigsten Fall kann das nächste Element nach einem Vergleich an der richtigen Position eingefügt werden. Es gilt dann:

T_best(n) = n-1