T
Hallo SG1,
habe meine quicksort jetzt verbessert
static void qs(void *links, void *rechts, size_t size, cmp_fct compare)
{
char *i = links;
char *j = (char *) rechts - size;
if (((char *) rechts - (char *) links) / size + 1 <= 16) /* Felder mit max. 16 Feldern mit insertionsort sortieren */
return insertionsort(links,
((char *) rechts - (char *) links) / size + 1,
size, compare);
char *pivot = median_of_three(links, rechts, size, compare);
if (pivot != rechts)
swap(pivot, rechts, size);
pivot = rechts;
do {
while (compare(i, pivot) < 0) /* i < pivot */
i += size;
while (compare(j, pivot) >= 0 && j >= links) /* j >= pivot */
j -= size;
if (i < j)
swap(i, j, size);
} while (i <= j); /* bis i > j */
swap(pivot, i, size);
if (j - (char *) links > (char *) rechts - (i + size)) { /* Rekursion immer zuerst mit dem kleineren Restfeld fortführen,
um den Aufrufstacl zu entlaste */
if (links < j)
qs(links, j, size, compare);
if (i + size < rechts)
qs(i + size, rechts, size, compare);
} else {
if (i + size < rechts)
qs(i + size, rechts, size, compare);
if (links < j)
qs(links, j, size, compare);
}
}
Aber irgendwo ist immer noch der Wurm drin.
C-Quicksort
=============
Sortierdauer bei 10000 Elementen (in sec):
Best case: 0.00
Mid case: 0.00
Worst case: 0.01
Sortierdauer bei 100000 Elementen (in sec):
Best case: 0.03
Mid case: 0.06
Worst case: 0.04
Heapsort
==========
Sortierdauer bei 10000 Elementen (in sec):
Best case: 0.01
Mid case: 0.00
Worst case: 0.01
Sortierdauer bei 100000 Elementen (in sec):
Best case: 0.08
Mid case: 0.10
Worst case: 0.09
Quicksort
===========
Sortierdauer bei 10000 Elementen (in sec):
Best case: 0.00
Mid case: 0.00
Worst case: 0.19
Sortierdauer bei 100000 Elementen (in sec):
Best case: 0.04
Mid case: 0.06
Worst case: 17.78
Habe swap und median_of_three auf inline erzeugen lassen, aber der Algorithmus scheint noch nicht perfekt. Hints anyone?
Gruß Tobias
