BohYoh.comトップページへ

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

戻る  

演習6-8の解答

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

/* 演習6-8 2分挿入ソート(要素の移動にmemmove関数を利用) */ #include <stdio.h> #include <string.h> #define swap(type, x, y) do {type t; t = x; x = y; y = t; } while (0) /*--- 2分挿入ソート ---*/ 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); }


戻る