prev up next


Previous: Sortieren Up: Sortieren Next: Bubblesort

Selection Sort

``Hole jeweils das kleinste Element nach vorne'' Source: SelectionSort.java     JavaDoc: SelectionSort.html    

Beispiel:

4 9 3 2 5
2 9 3 4 5
2 3 9 4 5
2 3 4 9 5
2 3 4 5 9

Analyse für Selection Sort

Worst case und average case:
Zwei ineinander geschachtelte for-Schleifen

n - 1 + n - 2 + n - 3 +...+ 1

= $\displaystyle\sum_{i=1}^{ n-1}$i = $\displaystyle{\frac{n (n-1)}{2}}$ = $\displaystyle{\frac{n^{2}}{2}}$ - $\displaystyle{\frac{n}{2}}$ = O(n 2)

Platzbedarf: O(n)
zusätzlich zu den Daten: O(1)

Der Algorithmus wird nicht schneller, wenn die Zahlen bereits sortiert sind!


prev up next
Previous: Sortieren Up: Sortieren Next: Bubblesort