Selection - Sort
Erklärung: http://www.delphiseiten.de/lex10/sort/selection.html
Beispiel 1: $a=array(1=>6,5,2,1,3,4,0); -> SelectionSort-Beispiel
Analyse des Sortieralgorithmus
| Code | Wiederh. | Bewegungen | Abfragen |
|---|---|---|---|
| for ($i=1; $i<=count($array)-1; $i++){ | n-1 | ||
| $minpos=$i; | n-1 | ||
| for ($j=$i+1; $j<=count($array); $j++){ | n-1+..+1 | ||
| if ($array[$j]<$array[$minpos]){ | n-1+..+1 | ||
| $minpos=$j; | Max.: n-1+..+1 Min.: 0 |
||
| } | |||
| } | |||
| $tmp=$array[$minpos]; | n-1 | ||
| $array[$minpos]=$array[$i]; | n-1 | ||
| $array[$i]=$tmp; | n-1 | ||
| } |
Best Case=2*(n-1)+ 2*n*(n-1)/2+3*(n-1)=n2+4*n-5
Worst Case=n2+4*n-5+n*(n-1)/2=3/2*n2+7/2*n-5
SelectionSort liegt somit in der Komplexitätsklasse O(n2)!