Sortierverfahren

Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren. Voraussetzung ist, dass auf der Menge der Elemente eine Ordnungsrelation definiert ist, die verschiedene gleichartige Objekte erlaubt, ansonsten aber eine eindeutige Reihenfolge festlegt. Diese Voraussetzung ist zum Beispiel bei der lexikographischen Ordnung von Zeichenketten oder der numerischen Ordnung von Zahlen erfüllt.

Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten. Die Komplexität eines Algorithmus, also die Anzahl der nötigen Operationen, wird üblicherweise in der Landau-Notation (später...) dargestellt. Einige Sortierverfahren benötigen außerdem neben dem zur Speicherung des Arrays nötigen noch weiteren Speicherplatz. Komplexität und Speicherbedarf hängen bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bester Fall), Average Case (Durchschnittsverhalten) und Worst Case (schlechtester Fall).

Man unterscheidet zudem zwischen stabilen und instabilen Sortierverfahren. Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern, während instabile Sortierverfahren diese Reihenfolge ändern können.

Zudem unterscheidet man zwischen Sortierverfahren, die in-place (auch in situ) arbeiten, d.h. die ohne zusätzlichen Speicherplatz funktionieren, und solchen, die dies nicht tun.

» drucken: pdf | html