STEP 9.1　シェルソート　(挿入ソートの改良）

<解説>　整列前の列について、ある間隔(gap, h)ごとの要素を、挿入ソートで整列する。

gapの適切な初期値、gapを繰り返して小さくしていく適切な数式については研究中。たとえば、gap(0) = N/3 + 1 gap(N) = gap(N-1)/3 + 1がよいという説もある。

<問題> N=8の列について、gapが、N/2ずつ小さくなるシェルソートを作成せよ。

<実行結果 例>　
start: 31 15 22 18 36 55 3 7　　　 　　　　　　（ソート前。要素数は8)
gap = 4, grp = 0 : 31 15 22 18 36 55 3 7　　 (gap = 4, 0から4とび) (31と36のソートなので、変化なし))
gap = 4, grp = 1 : 31 15 22 18 36 55 3 7　　 (gap = 4, 1から４とび)(15と55のソートなので、変化なし)
gap = 4, grp = 2 : 31 15 3 18 36 55 22 7　　 (gap = 4, 2から4とび) (22と3のソートなので、変化している)
gap = 4, grp = 3 : 31 15 3 7 36 55 22 18
gap = 2, grp = 0 : 3 15 22 7 31 55 36 18　　 (gap = 2。0から２とび）
gap = 2, grp = 1 : 3 7 22 15 31 18 36 55　　
gap = 1, grp = 0 : 3 7 15 18 22 31 36 55 　　(gap = 1。0からしかなく、これでソートは終了。この場合のソートは挿入ソートそのもの)

(プログラム内で、ソート前のデータを定義しています） 
解答例
/* shellsort by Shell, D. (1959) */
#include <stdio.h>
#define N 8

int S[N] = {31, 15, 22, 18, 36, 55, 3,7};

void insertion_sort(int n, int gap, int grp);
void print_array (int n);

void print_array (int n) {
   int i;
   for (i = 0; i < n; i++)
      printf("%3d", S[i]);
   printf("\n");
}

void insertion_sort (int n, int gap, int grp) { /* gapとびの配列, grp分ずれのグループをソート 教科書では間隔hのソート ,h-sortと表現することが多い */   int i, j, temp;
   for (i = gap + grp; i < n; i = i + gap) { /* gap+grpから、gapとび*/
      for (j = i; j >= gap; j = j - gap) {  /* 最後尾についてinsertion sort */
         if (S[j - gap] < S[j])  /* 正しく、後ろが大きい */
            break;               /* その位置に挿入してよかったかをチェック */
         /* swap */
         temp = S[j - gap];      /* 交換して、前進。*/
         S[j - gap] = S[j];
         S[j] = temp;
      }
   }
}

int main (void) {
   int gap, grp;

   printf("start:"); print_array(N);

   gap = N / 2;  /*  間隔は、N/2から、だんだんと小さく。やがて1へ */
   while (gap > 0) {
      for (grp = 0; grp < gap; grp++) {  /* gapは固定。そこからずれgrpを増加 */
         insertion_sort(N, gap, grp);
         printf("gap = %3d, grp = %3d :", gap, grp);
         print_array(N);
      }
      gap = gap / 2;
   }

   return 0;
}