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

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