3D sorting (C implementation)

Question

I am trying to implement some of the algorithms that are clean using C. I adhere to 3-way quicksort, but somehow the implementation does not give the correct result. The result is almost sorted, but some keys are not where it should be. The code is below. Thank you in advance.

#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; } 

sample output:

  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

Answer 1

After reading the link to the book you provide @JohnBollinger. I understand how your algorithm works. Your problem is that your rotation is moving, but you are not changing the value of v . Your core is in the lt index

 char *ptr = base; int lt = lo, gt = hi; // lt is the pivot int i = lo + 1; // we don't compare pivot with itself while (i <= gt) { int c = cmp(ptr + lt * size, 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); 

I offer you the “right” solution:

 #include <stdio.h> #include <stdlib.h> #include <time.h> typedef void qsort3way_swap(void *a, void *b); typedef int qsort3way_cmp(void const *a, void const *b); static void qsort3way_aux(char *array_begin, char *array_end, size_t size, qsort3way_cmp *cmp, qsort3way_swap *swap) { if (array_begin < array_end) { char *i = array_begin + size; char *lower = array_begin; char *greater = array_end; while (i < greater) { int ret = cmp(lower, i); if (ret < 0) { swap(i, lower); i += size; lower += size; } else if (ret > 0) { greater -= size; swap(i, greater); } else { i += size; } } qsort3way_aux(array_begin, lower, size, cmp, swap); qsort3way_aux(greater, array_end, size, cmp, swap); } } static void qsort3way(void *array_begin, void *array_end, size_t size, qsort3way_cmp *cmp, qsort3way_swap *swap) { qsort3way_aux(array_begin, array_end, size, cmp, swap); } static void swap_int_aux(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } static void swap_int(void *a, void *b) { swap_int_aux(a, b); } static int cmp_int_aux(int const *a, int const *b) { if (*a < *b) { return 1; } else if (*a > *b) { return -1; } else { return 0; } } static int cmp_int(void const *a, void const *b) { return cmp_int_aux(a, b); } static void print_int(char const *intro, int const *array, size_t const size) { printf("%s:", intro); for (size_t i = 0; i < size; i++) { printf(" %d", array[i]); } printf("\n"); } #define SIZE 42 int main(void) { int array[SIZE]; srand((unsigned int)time(NULL)); for (size_t i = 0; i < SIZE; i++) { array[i] = rand() % SIZE - SIZE / 2; } print_int("before", array, SIZE); qsort3way(array, array + SIZE, sizeof *array, cmp_int, swap_int); print_int("after", array, SIZE); } 

Note. Optimization int i = lo + 1; and char *i = array_begin + size; are required. Because in the case where the compare return function returns pivot != pivot , this will result in infinite recursion. How is this possible?

• The cmp function is a bug.
• double has a strange power ... Double may not be equal to itself! (-nan).

Answer 2

The implementation does not give the correct result, because this is not true. In fact, this is very bad, given that it should be tripartite speed, and not regular.

One of the main problems is that you lowered the bit in which you move the support bar to the correct position after the main sectioning cycle. For standard quick sorting, which requires one additional exchange or destination after the cycle, depending on implementation details. For a three-way quick sort, which includes one or two additional cycles, to move potentially many values ​​equal to the rotary value in their position.

A more insidious problem is what @Stargateur first pointed out: you track the rotation element with a pointer, not by value, and you (sometimes) change the original value from this position during the sectioning cycle.

In addition, your main partitioning cycle is incorrect for three-way quicksort. When you encounter an element equal to the axis, you just leave it in place, but you need to instead move it to one end or the other (or to some kind of auxiliary storage if you want to take on this memory cost), so what you can do this move to the middle at the end. In a sense, the previous problem is a special case of this — you are not making a reservation for or tracking turn values. Fixing this will also solve the previous problem.

I'm not sure which link you used to prepare your implementation, or you created it from scratch, but Geeks for Geeks has C ++ (but pretty much also C) for int arrays that you can check.