shellSort  シェルソート

void shellSort(DATA *data, int nmem, int asdes);

typedef struct {
    int key;        /* 比較のキーとなるフィールド */
    int info;       /* その他のフィールド */
} DATA;

data   （入出力）データレコードの配列
nmem   （入力）　レコード配列の大きさ
asdes  （入力）　昇順・降順別、0:昇順, 1:降順

なし

void shellSort(DATA *data, int nmem, int asdes)
{
    int i, j, k;
    int h;
    DATA t;

    for (h = 1; h <= nmem; h = 3*h + 1);

    while ((h = h/3) >= 1) {
        for (i = h; i < nmem; i++) {
            t.key = data[i].key;
            t.info = data[i].info;
            for (j = i - h; j >= 0; j -= h)
                if (asdes == 0) {
                    if (data[j].key > t.key) {
                        data[j+h].key = data[j].key;
                        data[j+h].info = data[j].info;
                    } else break;
                } else {
                    if (data[j].key < t.key) {
                        data[j+h].key = data[j].key;
                        data[j+h].info = data[j].info;
                    } else break;
                }
            data[j+h].key = t.key;
            data[j+h].info = t.info;
        }
    }
}

そのアイデアとしては、h要素分だけ離れた要素同士をまずソートし、h の値をだんだん小さくしながらソートを繰り返す。最後には、h=1でソー トする。