Problem with quicksort function on arrays of 64 bits integers in C

Question

I am currently working in C with large sets of 64-bit integers, and I naturally need a quicksort algorithm to simplify any incoming function on those sets. I tried a classic implementation already found in several places on this website (such as here) and ended up with the following code:

#include <stdio.h>
#include <stdlib.h>         
#include <time.h>
#include <stdint.h>

static void swap_int(uint64_t *a, uint64_t *b)
{
    uint64_t tmp = *a;
    *a  = *b;
    *b = tmp;
}

uint64_t QuickSortPartition(uint64_t *array, uint64_t begin, uint64_t end) {

    uint64_t i = begin, j;

    for (j = begin; j <= end; j++)
    {
        if (array[j] < array[end])
            swap_int(array + j, array + i++);
    }
    swap_int(array + i, array + end);

    return i;
}

void QuickSortFunction(uint64_t *array, uint64_t begin, uint64_t end) {
    if (begin < end) {
        uint64_t pivot = QuickSortPartition(array, begin, end);
        QuickSortFunction(array, begin, pivot - 1);
        QuickSortFunction(array, pivot + 1, end);
    }
}

It works perfectly fine for small sets as far as I have tested. I then went on to pseudorandomly generate 64 bits integers using the following function, and test the quicksort:

uint64_t rnd64(uint64_t n)
{
    const uint64_t z = 0x9FB21C651E98DF25;

    n ^= ((n << 49) | (n >> 15)) ^ ((n << 24) | (n >> 40));
    n *= z;
    n ^= n >> 35;
    n *= z;
    n ^= n >> 28;

    return n;
}

int main(int argc, char const *argv[]) {
    int n = 64;
    uint64_t Size = strtoull(argv[1], NULL, 10);

    uint64_t *S = malloc(Size * sizeof(uint64_t));

    uint64_t state = 1;
    for (uint64_t i = 0; i < Size; i++)
    {
        const uint64_t n = rnd64(state++);
        S[i] = n;
    }

    QuickSortFunction(S, 0, Size - 1);

    printf("Sorted S:\n");
    Display_set(S, Size, n);
}

Where Size is arbitrarily entered as an argv parameter. Moreover, Display_set is a standard function printing each element of S in binary and in order. This works perfectly fine for Size <= 11, but once Size = 11, this produces a segmentation fault. What am I doing wrong here?

I tried implementing other standard quicksort methods such as the pivot in first or last position, to no avail. As this function should (unless I am also wrong here) work for int type, I am guessing the transition to uint64_t induces an error.

Answer 1

You don't have to reinvent the wheel; check out the C standard library function qsort. It lets you specify the size of the elements, which you can set to sizeof(your integer type).

If quicksort isn't the algorithm you want, its sister functions mergesort and heapsort may be more useful.

The comparison function -- the last argument -- can be simply implemented as

int compare_int_type(const void *a, const void *b) {
    return *(const int_type *)a - *(const int_type *)b;
}

qsort is then called as

// for the last argument, you're passing the function,
// so it's important not to write compare().
qsort(array, size, sizeof(*array), compare);