跳到主要内容

電気通信大学 情報理工学研究科 情報学専攻 2020年8月実施 選択問題 アルゴリズムとデータ構造

标签：

Author​

GPT-5.6 Sol

Description​

次の C 言語で書かれた四つの関数 algo1 から algo4 は、要素数 の配列 d を昇順にソートする。swap は参照渡しされた二つの変数の値を交換する関数である。

void algo1(int d[], int n) {
    int i, k;

    for (k = 1; k < n; k++)
        for (i = 0; i < n-k; i++)
            if (d[i] > [ (a) ])
                swap(&d[i], &[ (a) ]);
}

void algo2(int d[], int n) {
    int i, k, m;

    for (k = n-1; k > 0; k--) {
        m = 0;
        for (i = 1; i <= k; i++)
            if (d[i] > d[m]) m = i;
        swap(&[ (b) ], &d[m]);
    }
}

void algo3(int d[], int n) {
    int i, j, x;

    for (i = 1; i < n; i++) {
        x = d[i]; j = i;
        while (d[j-1] > x && j >= 1) {
            d[j] = d[j-1]; j--;
        }
        if (j != i)
            d[j] = x;        /* (X) */
    }
}

void algo4(int d[], int n) {
    int i, j, x, g;

    for (g = n/2; g > 0; g = g/2)
        for (i = g; i < n; i++) {
            x = d[i]; j = i;
            while (d[j-g] > x && j-g >= 0) {
                d[j] = d[j-g]; j -= g;
            }
            if (j != i)
                d[j] = x;    /* (Y) */
        }
}

ソート対象は次の配列とする。

A = {1, 5, 3, 7, 2, 4, 6, 9, 8}
B = {8, 4, 7, 9, 3, 1, 5, 2, 6}
C = {9, 8, 7, 6, 5, 4, 3, 2, 1}
  1. algo1 はバブルソートを実現している。空欄 (a) を埋めよ。
  2. 配列 A と B を algo1 でソートするとき、swap が 8 回実行された直後の各配列を示せ。
  3. を満たす配列を algo1 でソートするとき、swap の実行回数を答えよ。
  4. algo2 の空欄 (b) を埋めよ。
  5. algo2 では algo1 より swap の実行回数が少なくなる。その理由をアルゴリズムの観点から述べよ。
  6. 配列 C を algo3 でソートするとき、(X) 行の実行回数を答えよ。
  7. 配列 C を algo4 でソートするとき、(Y) 行の実行回数を答えよ。
  8. algo4 が algo3 より配列要素の入れ換え回数を減らすために用いている工夫を述べよ。

Kai​

なお、C 言語の短絡評価で範囲外アクセスを避けるには、二つの while の条件をそれぞれ j >= 1 && d[j-1] > x、j-g >= 0 && d[j-g] > x の順に書く必要がある。以下ではこの意図で実行過程を追う。

(1)​

隣接要素 d[i] と d[i+1] を比較して交換するので、

(a) = d[i+1]

である。

(2)​

配列 A の転倒数は 8 であるため、8 回目の交換で整列が完了する。

A: 1 2 3 4 5 6 7 8 9

配列 B では、第 1 パスで 7 回交換した後、次のパスで 8 と 3 を交換した時点が 8 回目である。

B: 4 7 3 8 1 5 2 6 9

(3)​

配列は狭義の降順であり、すべての要素対が転倒している。バブルソートは一回の隣接交換で転倒を一つだけ除くので、交換回数は

である。

(4)​

各反復で添字 から の最大要素を d[k] に置くので、

(b) = d[k]

である。

(5)​

algo1 は転倒している隣接要素を見つけるたびに交換するため、最悪で 回交換する。 一方 algo2 は未整列部分の最大要素を探索し、外側ループ一回につき高々一回の交換でその要素を最終位置へ置く。したがって交換回数は高々 回である。

(6)​

algo3 は挿入ソートである。配列 C は降順なので、 のすべてで要素を前方へ移動し、(X) 行を一回ずつ実行する。よって

回

である。

(7)​

ギャップごとの (Y) 行の実行回数と処理後の配列は次のとおりである。

ギャップ (Y) の回数処理後の配列
451 4 3 2 5 8 7 6 9
221 2 3 4 5 6 7 8 9
101 2 3 4 5 6 7 8 9

したがって合計は

回

である。

(8)​

algo4 は Shell sort である。最初から隣接要素だけを扱わず、大きなギャップ で離れた要素から挿入ソートする。 これにより、本来の位置から遠い要素を一度に長い距離だけ移動して転倒を先に減らせる。最後に の通常の挿入ソートを行う時点では配列がほぼ整列済みであるため、要素の移動回数が少なくなる。

目录