Laufzeitkomplexität

Die Komplexität des SelectionSorts ist der des Bubble- oder InsertionSorts gleich. Auch er muss $n~-~1$ Durchläufe durch die Datenmenge ausführen. Um das kleinste Element in der verbleibenden unsortierten Menge sind $\frac{k\times(k + 1)}{2}$ Arbeitsschritte notwendig, wobei ``k'' die Anzahl der unsortierten Elemente bezeichnet. Eingesetzt und aufgelösst ergibt sich somit $\frac{n^2~-~n}{2}$ für den SelectionSort. In der O-Notation: $O(n^2)$.

Man beachte, das eine Optimierung des Algorithmus im Allgemeinen nicht möglich ist, und dieser im avarage wie im worst case immer gleich viel Schritte benötigt.

Die folgende Tabelle spiegelt einige Werte für die Anzahl der Vergleichs- und Tauschoperationen. Zu beachten ist, dass die Anzahl der Tauschoperationen im Vergleich zum Insertion- oder BubbleSort drastisch durch die Verwendung des SelectionSorts reduziert werden kann, wie in der Tabelle ersichtlich wird. Die Tests wurden immer auf der gleichen Datenmenge durchgeführt, welche mit zufälligen Zahlen gefüllt war.


Elemente Vergleiche Tauschoperationen
5 10 1
10 45 8
100 4950 95
1000 499500 997
10000 49995000 9992

Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: QuickSort Aufwärts: SelectionSort Vorherige Seite: Implementierung   Inhalt

2002-05-09