BG/BRG Lerchenfeld
Schulbezeichnung
Impressum |  Kontakt |  Neues |  Sitemap

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)!