Tag Archives: Shellsort

Shellsort in C

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