C言語プログラミング3(シェルソート)

「C言語プログラミング2(挿入ソート)」に続きまして、またソート(つまりばらばらの順番に並んだデータを並べ替えること)のお話です。
今回ご紹介するのはシェルソート(改良挿入ソート)と言いまして、前回の挿入ソートの改良版です。
挿入ソートには「用意されているデータがある程度整列されているときは高速である」という長所がある代わりに「用意されているデータが整列状態と遠いほど低速となる」という欠点があります。
シェルソートはその欠点を改善するため、いきなり全体に挿入ソートをするのではなく、部分毎に挿入ソートを行います。
そして、その部分を徐々に広げていき、最終的にある程度整列された状態で挿入ソートをするというものです。

データが「８５４２６３７１」のときの数値の変化例を以下に書いてみます。

まず、データとデータの間隔を4として挿入ソートを行う。
・1番目の数値と5番目の数値で挿入ソート。「(６)５４２(８)３７１」
・2番目の数値と6番目の数値で挿入ソート。「６(３)４２８(５)７１」
・3番目の数値と7番目の数値を挿入ソート。「６３(４)２８５(７)１」
・4番目の数値と8番目の数値を挿入ソート。「６３４(１)８５７(２)」
次に、データとデータの間隔を2として挿入ソートを行う。
・1番目から3番目と5番目と7番目の数値で挿入ソート。「(４)３(６)１(７)５(８)２」
・2番目から4番目と6番目と8番目の数値で挿入ソート。「４(１)６(２)７(３)８(５)」
次に、データ間隔1として挿入ソートを行う。
・全データでの挿入ソート。「１２３４５６７８」

以下、C言語で書いたシェルソートのプログラムを掲載します。
ソートを行う関数部分のみです。

/* シェルソート関数ここから */
/* data[]:データ格納配列　num:配列要素数 */
void sort(int data[],int num){
int i,j,n,temp;
for(n=num/2;n>0;n=n/2){/*間隔を徐々に狭めていく　最終的には1*/
for(i=n;i<num;i++){/*nで決まっている間隔で一つずつ挿入ソート*/
temp=data[i];
/*temp以下の値が出るまで配列を右にずらす*/
for(j=i;j>n-1;j=j-n){
if(temp>data[j-n])break;
data[j]=data[j-n];
}
data[j]=temp;
}
}
}

Wikipedia ソート
Wikipedia シェルソート
Wikipedia C言語