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