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 best case:
Zwei ineinander geschachtelte for-Schleifen

$$n-1+n-2+n-3+\ldots +1$$

$$= \sum_{i=1}^{ n-1} i = \frac {n (n-1)}{2}= \frac{n^{2}}{2} - \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!