Wie gesagt wird Quicksort bei so einem kleinen Array nicht wirklich schneller sein. Gerade weil der Funktionsaufruf durch die Sicherung auf dem Stack viel kostet. Quicksort lebt davon, dass es (anders als die einfachen Vergleichs-Algorithmen) Stellen vertauscht die weit auseinanderliegen. Das ist hier nicht gegeben. Bei großen Arrays ist das allerdings super.
Viele fertige Sortier-Methoden in Hochsprachen schalten je nach Datentyp und Größe des zu sortierenden Arrays zwischen Quicksort oder Mergesort für große Arrays und Insertionsort (oder eine Variante davon) für kleine um.
Du kannst mal Insertionsort ausprobieren. Das ist vielleicht ein klein wenig schneller und ist ähnlich einfach wie Bubblesort:
Das braucht pro Schritt glaube ich ein paar Operationen weniger als Bubblesort. Ob man das hier merkt hier was anderes.
Das ist in dem Link für einen Vektor implementiert (und damit eigentlich für C++ und nicht C), aber geht genau mit einem Array (bis auf das .length natürlich)
Bei einem Array aus 10 Byte ( random Werte 0 .. 255 ) braucht qsort ca. 3 mal so lang wie bubblesort.
Natürlich braucht das Erzeugen von 10 Random Werten wesentlich länger, dagegen fällt das Sortieren (egal wie) kaum ins Gewicht.
1378 µs without sort, calling a dummy sort function
1427 µs with bubblesort -> 49 µs
1537 µs with qsort -> 159 µs
Wenn beim Einsortieren eines einzelnen Werts auch bis zur Hälfte der bereits vorhandenen Daten umkopiert werden müssen, liegt das übrigens in der gleichen Größenordnung.
( 10 µs sind da etwas optimistisch geschätzt gewesen )
Es ist auch gut möglich, dass qsort() rekursiv implementiert ist. Das kostet dann zusätzlich zur Vergleichsfunktions nochmal Zeit. Man kann es aber auch iterativ implementieren.
Aber generell wird Quicksort nicht für kurze Listen/Arrays empfohlen, egal wie es implementiert ist.
Wobei man je nach Anwendung auch mit 160µs leben kann und dann nichts selbst machen muss
Bei PerformanceTests / Benchmarks wird die Richtigkeit der Ergebnisse üblicherweise nicht geprüft.
Ich hab mal die Version mit den wenigsten Buchstaben genommen ( c Version von hier )
void sort(byte* a, byte n)
{
// qsort (a, n, 1, compare);
// return;
// bubblesort
byte j, t = 1;
while (n-- && t)
for (j = t = 0; j < n; j++) {
if (a[j] <= a[j + 1]) continue;
t = a[j], a[j] = a[j + 1], a[j + 1] = t;
t = 1;
}
}
int compare (const void * a, const void * b)
{ return (*(byte*)a - *(byte*)b ); }
Aufruf mit einem frisch erzeugten Array aus random(256) bytes.
Klar könnte man auch eine manuell an die Gegebenheiten angepasste qsort Variante schreiben, ohne externe compare-Funktion.
Aber das wäre dann gegen Chris' Kriterium der Minimierung der Quellcode-Zeilen .
Ah, das ist mal ne super Seite. Funktionierender Code in allen möglichen Sprachen Muss ich mir mal merken
Die bessere Version für kleine Arrays ist wie gesagt Insertionsort:
Auch in der Komplexitäts-Klasse O(n²), aber man braucht weniger Operationen, u.a. weil nicht in jedem Durchgang das ganze Array umkopiert wird. Insertionsort ist auch besser mit Arrays die fast sortiert sind. Das ist auch was viele fertige Libs für kleine Arrays nehmen oder dazu wechseln wenn Quicksort bei kleinen Teil-Arrays angekommen ist
Natürlich kann man sagen, dass es für 10 Elemente völlig egal ist, aber gerade Anfängern sollte man nicht unbedingt Algorithmen beibringen, die nur unter ganz bestimmten Umständen brauchbar sind.
bei einem Bubblesort würde ich immer einen Test einbauen, ob in dem letzten Durchgang überhaupt ein Element getauscht wurde. Bei vorsortierten Feldern kann man so nach ganz wenigen Durchgängen fertig sein. Bei richtiger Programmierung ist ein neues Element bei einem sortiertem Array in einem Durchgang einsortiert.
