Quicksort de 3 vias (implementação C)
eu tentoimplemento alguns algoritmos são genéricos puros usando C. Eu uso o quicksort de três maneiras, mas de alguma forma a implementação não fornece a saída correta. A saída quase ordenou, mas algumas chaves não estão onde deveriam estar. O código está abaixo. Desde já, obrigado.,
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
static void swap(void *x, void *y, size_t size) {
void *tmp = malloc(size);
memcpy(tmp, x, size);
memcpy(x, y, size);
memcpy(y, tmp, size);
free(tmp);
}
static int cmpDouble(const void *i, const void *j) {
if (*(double *)i < *(double *)j)
return 1;
else if (*(double *)i == *(double *)j)
return 0;
else
return -1;
}
void qsort3way(void *base, int lo, int hi, size_t size,
int (*cmp)(const void *, const void *)) {
if (hi <= lo)
return;
else {
char *ptr = (char*)base;
char *v = ptr + lo * size;
int lt = lo, gt = hi;
int i = lo;
while (i <= gt) {
int c = cmp(v, ptr + i * size);
if (c < 0)
swap(ptr + (lt++) * size, ptr + (i++) * size, size);
else if (c > 0)
swap(ptr + i * size, ptr + (gt--) * size, size);
else
i++;
}
qsort3way(base, lo, lt - 1, size, cmp);
qsort3way(base, gt + 1, hi, size, cmp);
}
}
int main(void) {
int i;
double *d = (double*)malloc(sizeof(double) * 100);
for (i = 0; i < 100; i++)
d[i] = (double)rand();
qsort3way(d, 0, 100 -1, sizeof(double), cmpDouble);
for (i = 0; i < 100; i++)
printf("%.10lf\n", d[i]);
free(d);
return 0;
}
saída de amostra:
41.0000000000 153.0000000000 288.0000000000 2082.0000000000 292.0000000000 1869.0000000000 491.0000000000 778.0000000000 1842.0000000000 6334.0000000000 2995.0000000000 8723.0000000000 3035.0000000000 3548.0000000000 4827.0000000000 3902.0000000000 4664.0000000000 5436.0000000000 4966.0000000000 5537.0000000000 5447.0000000000 7376.0000000000 5705.0000000000 6729.0000000000 6868.0000000000 7711.0000000000 9961.0000000000 8942.0000000000 9894.0000000000 9040.0000000000 9741.0000000000