シェルソート

シェルソート

　『うかる! 基本情報技術者 [午後・アルゴリズム編] 福嶋先生の集中ゼミ』に、シェルソートの説明がありました。プログラムは下に引用させてもらったものと同じようなものだと思います。
　j　の内側のループで、「なんでマイナスなんだろう」と思ったのですが、数値を入れ替えた時に、その前のソート済みの部分より入れ替えた数字の方がまだ大きかった場合に、そこも並べ替えておかないといけないので、並べ替えたデータより前が小さいデータだけになるように、遡ってデータの大きさを比較していかなければならないからの様です。

シェルソート Cプログラム

『Ｃ言語講座』（http://www1.cts.ne.jp/~clab/hsample/Sort/Sort4.html）より引用

#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; 
            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");
}

出力結果

ソート前
8  7  6  5  4  3  2  1

4  7  6  5  8  3  2  1
4  3  6  5  8  7  2  1
4  3  2  5  8  7  6  1
4  3  2  1  8  7  6  5

2  3  4  1  8  7  6  5
2  1  4  3  8  7  6  5
2  1  4  3  6  7  8  5
2  1  4  3  6  5  8  7

1  2  4  3  6  5  8  7
1  2  3  4  6  5  8  7
1  2  3  4  5  6  8  7
1  2  3  4  5  6  7  8


ソート後
1  2  3  4  5  6  7  8