Sortieralgorithmen

In diesem Abschnitt gehen wir davon aus, dass die zu sortierenden Datensätze in einem Feld f der Größe N in aufsteigender Reihenfolge sortiert werden. Die Feldelemente sollen in aufsteigender Reihenfolge sortiert werden.

Das Feld f dient als Eingabe für die Folge des Sortierverfahrens sowie als Ausgabedatenstruktur. Die Elemente müssen also innerhalb des Folge umsortiert werden. Nach dem Sortieren gilt für das Feld f:

f[1].wert <= f[2].wert ...<=f[N].wert

Beispiel

Unsortierte Folge mit N=7 Elementen:

Sortierte Folge mit N=7 Elementen

Bewertungskriterien

Bei der Bewertung der der Sortieralgorithmen wird jeweils in Abhängigkeit der Größe des zu sortierenden Feldes

  • die Anzahl der Schlüsselvergleiche C (englisch comparisons) und
  • die Anzahl der Bewegungen M (englisch: movements) der Elemente

gemessen.

Bei diesen zwei Parametern interessieren

  • der beste Fall (die wenigsten Operationen)
  • der schlechteste Fall (die meisten Operationen)
  • der durchschnittliche Fall

Schlüsselvergleiche sowie Bewegungen tragen beide zur Gesamtlaufzeit bei. Man wählt den größeren der beiden Werte um eine Abschätzung für die Gesamtlaufzeit zu erlangen.

Stabilität von Sortierverfahren

Ein weiteres Kriterium für die Bewertung von Sortiervorgängen ist die Stabilität.

Definition: Stabiles Sortierverfahren
Ein Sortierverfahren ist stabil wenn nach dem Sortieren die relative Ordnung von Datensätzen mit dem gleichen Sortierschlüssel erhalten bleibt.

Beispiel: Eine Folge von Personen die ursprünglich nach der Mitarbeiternummer (id) sortiert. Diese Folge soll mit dem Nachnamen als Sortierschlüssel sortiert werden.

Im folgenden Beispiel wurde ein stabiles Sortierverfahren angewendet. Die relative Ordnung der beiden Personen mit dem Namen "Schmidt" bleibt erhalten. Der Mitarbeiter mit der Nummer 18 bleibt vor dem Mitarbeiter mit der Nummer 21. 

Bei nicht stabilen Sortierverfahren bleibt diese relative Ordnung nicht unbedingt erhalten. Hier könnte eine sortierte Folge so aussehen:

nicht stabiles Sortierverfahren

Stabile Sortierverfahren erlauben das Sortieren nach mehreren Prioritäten da eine Vorsortierung erhalten wird.

Im oben gezeigten Beispiel kann man eine Folge

  • primär nach Nachnamen sortierten und
  • sekundär nach der Personalnummer (id).

Man sortiert die Personen zuerst nach dem Kriterium mit der niedrigen Priorität. Dies ist hier die Personalnummer. Diese Vorsortierung war schon gegeben. Anschließend sortiert man nach dem wichtigeren Kriterium, dem Nachnamen. Die so entstandene Folge ist primär nach Nachnamen sortieret, sekundär nach Personalnummer.