Tag Archives: Quicksort

Quicksort in C

Quicksort was invented by Tony Hoare and is one of the fastest known sorting algorithms. This is an implementation in C using the Lomuto partition scheme described in the Cormen book.

void memswap(void *array, size_t element_size, unsigned int first, unsigned int second, void *temp)
{
    if (first == second) {
        return;
    }
    memcpy(temp, array + first * element_size, element_size);
    memcpy(array + first * element_size, array + second * element_size, element_size);
    memcpy(array + second * element_size, temp, element_size);
}

static unsigned int partition(char *arr, unsigned int low, unsigned int high, size_t element_size,
        int (*compare)(const void *, const void *), void *temp)
{
    void *pivot = arr + high * element_size;
    unsigned int i = low;
    unsigned int j;
    for (j = low; j < high; j++) {
        if (compare(arr + j * element_size, pivot) <= 0) {
            memswap(arr, element_size, i, j, temp);
            i++;
        }
    }
    memswap(arr, element_size, i, high, temp);
    return i;
}

static void quicksort_recursive(void *arr, unsigned int low, unsigned int high, size_t element_size,
        int (*compare)(const void *, const void *), void *temp)
{
    if (low < high) {
        unsigned int p = partition(arr, low, high, element_size, compare, temp);
        quicksort_recursive(arr, low, p - 1, element_size, compare, temp);
        quicksort_recursive(arr, p + 1, high, element_size, compare, temp);
    }
}

void quicksort(void *arr, size_t len, size_t element_size, 
        int (*compare)(const void *, const void *))
{
    void *temp = malloc(element_size);
    if (!temp) {
        return;
    }
    quicksort_recursive(arr, 0, len - 1, element_size, compare, temp);
    free(temp);
}

Example program:

static int compare_chars(const void *v1, const void *v2)
{
    const char *p1 = v1;
    const char *p2 = v2;
    if (*p1 < *p2) {
        return -1;
    }
    if (*p1 > *p2) {
        return 1;
    }
    return 0;
}

int main(void)
{
    char str1[] = "QWERTYUIOP";
    const size_t len = strlen(str1);
    char *str2 = malloc(len + 1);
    strcpy(str2, str1);
    quicksort(str2, len, 1, compare_chars);
    printf("%s\n", str2);
    free(str2);
    return 0;
}