This is Robert Sedgewick’s implementation of shellsort, generalised to have the same interface as the standard qsort()
function.
void shellsort_internal(void *arr, int left, int right, size_t element_size, int (*compare)(const void *, const void *)) { int i, j, k, h; int incs[] = { 1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1 }; void *v = malloc(element_size); if (!v) { return; } for (k = 0; k < 16; k++) { for (h = incs[k], i = left + h; i <= right; i++) { memcpy(v, arr + i * element_size, element_size); j = i; while (j >= h && compare(arr + (j - h) * element_size, v) > 0) { memcpy(arr + j * element_size, arr + (j - h) * element_size, element_size); j -= h; } memcpy(arr + j * element_size, v, element_size); } } free(v); } void shellsort(void *arr, size_t len, size_t element_size, int (*compare)(const void *, const void *)) { shellsort_internal(arr, 0, len - 1, element_size, compare); }
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); shellsort(str2, len, 1, compare_chars); printf("%s\n", str2); free(str2); return 0; }
Reference: Analysis of Shellsort and Related Algorithms