Ｃ言語によるアルゴリズムとデータ構造

演習6-7の解答

　配列の要素数が多い場合は、挿入作業に要する比較・交換の回数のコストは無視できない。目的列はソート済みであるので、まず挿入すべき位置を２分探索法によって調べて、その位置から後ろの要素を一つずつずらすことによっても挿入ソートを実現できる。
　このアイディアに基づいて挿入ソートを行うプログラムを作成せよ。
　なお、このソート法は、２分挿入ソート（binary insertion sort ）と呼ばれるアルゴリズムとして知られている。
※ただし、安定ではなくなることに注意せよ。

/*
    演習6-7
    ２分挿入ソート
*/

#include  <stdio.h>

/*--- ２分挿入ソート ---*/
void insertion(int a[], int n)
{
    int  i, j;

    for (i = 1; i < n; i++) {
        int  key = a[i];
        int  pl = 0;        /* 探索範囲先頭の添字 */
        int  pr = i - 1;    /* 　 〃 　末尾の添字 */
        int  pc;            /* 　 〃 　中央の添字 */
        int  pd;            /* 挿入すべ位置の添字 */

        do {
            pc = (pl + pr) / 2;
            if (a[pc] == key)       /* 探索成功 */
                break;
            else if (a[pc] < key)
                pl = pc + 1;
            else
                pr = pc - 1;
        } while (pl <= pr);
        pd = (pl <= pr) ? pc + 1 : pr + 1;

        for (j = i; j > pd; j--)
            a[j] = a[j - 1];
        a[pd] = key;
    }
}

int main(void)
{
    int  i;
    int  x[7];
    int  nx = sizeof(x) / sizeof(x[0]);
    
    printf("%d個の整数を入力せよ。\n", nx);
    for (i = 0; i < nx; i++) {
        printf("x[%d] : ", i);
        scanf("%d", &x[i]);
    }

    insertion(x, nx);                       /* 配列xを単純挿入ソート */

    puts("昇順にソートしました。");
    for (i = 0; i < nx; i++)
        printf("x[%d] = %d\n", i, x[i]);

    return (0);
}

戻る