シェルソート

シェルソート

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

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

『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

せっかく整列しているのに

 せっかく2列ずつで整列しているのに、見ての通り、2つの列を併合するときに、前から前から見ていって、列ごとにソートされているのが全く生かされていません。これだったら、データが偏っていたら、せっかくの整列がかなり無駄になってしまいます。
 人間が手作業で2列を合わせるのだったら、2つの列を見比べて、小さい方をどんどん取って並べていくのに、なんでそこを考えないんでしょう。
 マージソートの様に、2列を合わせる時に、大小を比較しながら合わせていく方が、絶対効率がいいと思うのに、そんな整列の仕方を書いた説明はどこにもありません。
 しかし、配列をもう一つ用意せずにそれをやろうとすると、かなり面倒くさそうですね。

タイトルとURLをコピーしました