Ｃ言語講座：シェルソート

/* シェルソートについて学びます。シェルとは何でしょう。開発者 D.L.Shell の名前からきています。アルゴリズムとしては、単純挿入ソートを改良したものです。このアルゴリズムでは、全体をおおざっぱにソートし、徐々に細かくソートを行うことになります。

このソート法では、要素を分割し、分割した各ブロックに対して、単純挿入ソートを行います。次いで、ブロックのサイズを大きくして、再度単純挿入ソートを行います。これを繰り返し、最後に全体を一つのブロックとして、単純挿入ソートを行うと、ソートが終了します。

要素数が 8 の配列を例にして、具体的に説明します。分割のブロックの数をしまうint 型の変数を gap とします。gap の初期値を '要素数 / 2' とします。gap の次の値は gap /= 2 とします。

下記の gap の値の通しナンバーのブロックに対して、単純挿入ソートを行います。

要素が10の配列では、gap の初期値は5で、2、1と変化します。

今回のソースプログラムでは、前回の単純挿入ソートを行う関数を、一部変えて再利用しています。 */

/* ここからソースプログラム */

#include <stdio.h>

#define NUM_DATA 8

void ShellSort(int num[ ], int n) ;
void InsSort(int num[ ], int gap, int n);
void ShowData(int num[ ], int n);
void main(void);

  /* n 個のデータのシェルソートを行う */
void ShellSort(int num[ ], int n)
{
    int gap;

    for (gap = n / 2; gap > 0; gap /= 2)
        InsSort(num, gap, n);
}

  /* n 個のデータの単純挿入ソートを行う */
void InsSort(int num[ ], int gap, int n)
{
    int i, j, temp;

    for (i = gap; i < n; i ++) {
        for (j = i - gap; j >= 0; j -= gap) { /* このループで */
            if (num[j] <= num[j + gap])     /* j 番目とj + gap 番目と比較 */
                break;       /* ここにbreak;を挿入。H.O.さんご指摘ありがとうございました。 */
            else {
                temp = num[j];                /* 要素の入れ替え */
                num[j] = num[j + gap];
                num[j + gap] = temp;
                ShowData(num, NUM_DATA);      /* 途中経過を表示 */
            }
        }
    }
    printf("\n");        /* InsSort(  ) を抜ける時改行 */
}

  /* n 個のデータの表示 */
void ShowData(int num[ ], int n)
{
    while (n--)
        printf("%d  ", *num++);
    printf("\n");
}

void main(void)
{
      /* ソート対象のデータ */
    int num[ ] = {8, 7, 6, 5, 4, 3, 2, 1 };	

      /* ソート前のデータの表示 */
    printf("ソート前\n");
    ShowData(num, NUM_DATA);
    printf("\n");

      /* シェルソート */
    ShellSort(num, NUM_DATA);
    printf("\n");

      /* ソート後のデータの表示 */
    printf("ソート後\n");
    ShowData(num, NUM_DATA);
    printf("\n");
}

/* ここまでソースプログラム */