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