Insertion - Sort
Der Algorithmus entnimmt der unsortierten Eingabefolge ein Element und fügt es geordnet an der richtigen Stelle in der Ausgabefolge ein. Wird auf einem Array gearbeitet, so müssen die Elemente hinter dem neu eingefügten Element verschoben werden.
Beispiel: $a=array(1=>6,5,2,1,3,4,0); -> InsertionSort-Beispiel
Analyse des Sortieralgorithmus
| Code | Wiederholungen | Bewegungen |
|---|---|---|
| for ($i=2; $i<=count($array); $i++){ | n-1 | |
| $tmp=$array[$i]; | n-1 | |
| $j=$i-1; | n-1 | |
| while (($j>0) && ($array[$j]>$tmp)){ | Max.: 2+..+n=(n+1)*n/2-1 Min.: n-1 |
|
| $array[$j+1]=$array[$j]; | Max.: 1+..+n-1=n*(n-1)/2 Min.: 0 |
|
| $j--; | Max.: 1+..+n-1=n*(n-1)/2 Min.: 0 |
|
| } | ||
| $array[$j+1]=$tmp; | n-1 | |
| } |
Best Case=5*(n-1)
Worst Case=4*(n-1)+n*(n+1)/2-1 +2*n(n-1)/2=3/2*n2+7/2*n-5
InsertionSort liegt somit in der Komplexitätsklasse O(n2)!