nicht angemeldet
Hallo Peter,
ein paar ergänzende Bemerkungen (auch für das Archiv). Wahrscheinlich weißt Du das eh' schon, da Du Dich offensichtlich intensiv mit Sortierverfahren beschäftigst.
Teilweise, es geht um Sortieralgorithmen. Die getesteten sind Bubblesort, Insertion sort und Selection sort mit O(n^2), Quicksort mit O(n log n)
für Quicksort im Durchschnitt. Worst Case für Quicksort ist O(n^2).
und mein Bitsort mit O(n). Daher auch hier die Bitfrage. Ein Test gerade hat ergeben (der jeweils zweite Wert bezieht sich auf die Sortierung der bereits sortierten Liste, d.h. den best case):
mit einer "naiven" Implementation ist die bereits sortierte Liste der worst case für Quicksort, siehe z.B. Wikipedia, Quicksort.
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;
}
}
Bitsort: 0.0652689933777 Sekunden.
Bitsort: 0.0693278312683 Sekunden.
Eine Implementierung einer Radix-Sort-Variante?
Die Zufallszahlen waren jeweils dieselben. PHP ist hier sicher nicht die optimale Wahl, reicht aber, um die Komplexitätsunterschiede zu zeigen.
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?
Freundliche Grüße
Vinzenz
Der Martin