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

\begin{displaymath}
n-1+n-2+n-3+\ldots +1\end{displaymath}


\begin{displaymath}= \sum_{i=1}^{ n-1} i = \frac {n (n-1)}{2}=
\frac{n^{2}}{2} - \frac{n}{2}= O(n^{2})\end{displaymath}

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