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

演習6-6の解答

　配列の先頭a [0]が使われていなくて、データがa [1]以降のみに格納されているとする。この場合、a [0]を番兵として用いれば、挿入走査の終了条件を緩和できることになる。
　このアイディアに基づいて単純挿入ソートを行う関数を作成せよ。

/*
    演習6-6
    単純挿入ソート（配列の先頭要素は空いている）
*/

#include  <stdio.h>

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

/*--- 単純挿入ソート（配列の先頭要素a[0]は空いている） ---*/
void insertion(int a[], int n)
{
    int  i, j;

    for (i = 1; i < n; i++) {
        int  tmp = a[0] = a[i];
        for (j = i; a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        if (j) a[j] = tmp;
    }
}

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

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

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

    return (0);
}

戻る