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

演習6-8の解答

　前問のアルゴリズムでは、挿入する位置の探索は高速に行えるが、その後、挿入のために要素を一つずつずらす作業のコストは、単純挿入法と同じである。
　要素をずらす作業をmemmove 関数を使って実現すれば、高速化が期待できる。このアイディアに基づいて２分挿入ソートを行う関数を作成せよ。

/*
    演習6-8
    ２分挿入ソート（要素の移動にmemmove関数を利用）
*/

#include  <stdio.h>
#include  <string.h>

#define swap(type, x, y)    do {type t; t = x; x = y; y = t; } while (0)

/*--- ２分挿入ソート ---*/
void insertion(int a[], int n)
{
    int  i, j;
int k;
    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;

        memmove(&a[pd + 1], &a[pd], (i - pd) * sizeof(int)); 
        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);
}

戻る