nicht angemeldet
Tag,
3000 Zufallszahlen: 0.0158278942108 Sekunden.
Insertion sort: 13.6109161377 Sekunden.
Insertion sort: 9.9717400074 Sekunden.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:
function insertion_sort (&$array, $anzahl) {
$i = $j = $v = 0;
for ($i = 1; $i < $anzahl; $i++) {
$v = $array[$i];
$j = $i;
while ($j > 0 && $array[$j-1] > $v) {
$array[$j] = $array[$j-1];
$j--;
}
$array[$j] = $v;
}
}
Das hat mich auch gewundert, aber ich habe:
~~~php
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;
}
}
Ich wüsste nicht, was daran falsch sein soll. So weit ich sehe, unterscheiden sich die Implementierungen nur in der (überflüssigen) Variablendeklaration und im Schleifentyp. Hab ich bei der for-Schleife einen Denkfehler gemacht? Ich hab Insertion sort noch nie mit for-Schleife gesehen, war aber der Meinung, dass es funktionieren müsste.
Bitsort: 0.0652689933777 Sekunden.
Bitsort: 0.0693278312683 Sekunden.Eine Implementierung einer Radix-Sort-Variante?
Ja, allerdings etwas verallgemeint, sodass man es auch für lexikografische Sortierung etc. verwenden kann. Ich wüsste daher nicht, was noch für die "traditionellen allgemeinen" Sortieralgorithmen spricht, meins ist dann ja auch ein solches.
Für die Komplexität der Verfahren wäre dies ein einziger Messpunkt. Ich weiß ja, dass Du mehrfach gemessen hast. Wäre es nicht eine nette Idee, per GD-Lib eine hübsche Grafik automatisiert erstellen zu lassen?
Wenn ich jetzt GDlib könnte. Ich hab mir gedacht, dass ich einfach ein paar Messreihen mache und das dann mit GnuPlot irgendwie hinbastle, wobei ich damit auch keine Erfahrung habe. Meinst du, GDlib wäre praktischer?
Danke,
Peter
Der Martin