シェルソートは、挿入ソートを改変したアルゴリズムである。シェルソートでは、まず適当な間隔 h を決めて、h、2h、3h、・・・ の位置にある要素に対して挿入ソートを適用する。次に、h の値を小さくし、もう一度 h、2h、3h、・・・の位置にある要素に対して挿入ソートを適用する。h = 1 のときに、最後にもう一回挿入ソートを適用して、整列を終える。

#include <stdio.h>

int shellSort(int array[], int array_size) {

    for (int h = array_size / 2; h > 0; h /= 2) {
        for (int i = h; i < array_size; i += 1) {
            int k = array[i];

            int j;
            for (j = i; j >= h && array[j - h] > k; j -= h) {
                array[j] = array[j - h];
            }

            array[j] = k;
        }
    }

    return 0;
}


int main (void) {
    int i;
    int array[10] = {3, 6, 1, 7, 2, 0, 4, 5, 9, 8};

    printf("       array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    shellSort(array, sizeof(array) / sizeof(array[0]));

    printf("sorted array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}