Bitweiser Zugriff

[Peter Thomassen]

Hallo

Du musst einen Fehler in Deinem Insertion Sort haben. Insertion Sort ist im besten Fall (vorsortierte Liste) linear. Folgende Funktion (nach Algorithmen, Robert Sedgewick, Addison-Wesley) tut dies zumindest:

Das hat mich auch gewundert, aber ich habe:

function insertionSort(&$a) {
for($i = 1; $i < count($a); $i++) {
  $focus = $a[$i];
  for($j = $i; $j > 0 && $a[$j - 1] > $focus; $j--) {
   $a[$j] = $a[$j - 1];
  }
  $a[$j] = $focus;
}
}

  
\*grr\* Erst denken, dann reden. count($a) wird bei jedem Schleifendurchlauf ausgeführt und macht's so quadratisch. Hab's mal in eine Varialbe ausgelagert.  
  
Bye,  
Peter