Coder Wiki | Algorithmen | Sortierverfahren

Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten. Die Komplexität eines Algorithmus, also die Anzahl der nötigen Operationen, wird üblicherweise in der O-Notation 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 dies nicht garantieren.

Sortierverfahren	Best-Case	Average-Case	Worst-Case	Stabil	Rekursiv
Bubblesort	O(n)	O(n²)	O(n²)	ja	nein
Heapsort	O(n·log(n))	O(n·log(n))	O(n·log(n))	nein	nein
Insertionsort	O(n)	O(n²)	O(n²)	ja	nein
Mergesort	O(n·log(n))	O(n·log(n))	O(n·log(n))	ja	ja
Quicksort	O(n·log(n))	O(n·log(n))	O(n²)	nein	ja
Selectionsort	O(n²)	O(n²)	O(n²)	ja	nein
RadixExchangeSort	O(n log N*)	O(n log N*)	O(n log N*)	nein	ja

Algorithmen

Sortierverfahren

Andere Links zu Sortierverfahren