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

标签：

• University-of-Electro-Communications
• Bubble-Sort
• Selection-Sort
• Insertion-Sort
• Shell-Sort

Author

GPT-5.6 Sol

Description

次の C 言語で書かれた四つの関数 algo1 から algo4 は、要素数 $n$ の配列 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. $d_k>d_{k+1}$ $(0\le k\le n-2)$ を満たす配列を algo1 でソートするとき、swap の実行回数を答えよ。
4. algo2 の空欄 (b) を埋めよ。
5. algo2 では algo1 より swap の実行回数が少なくなる。その理由をアルゴリズムの観点から述べよ。
6. 配列 C を algo3 でソートするとき、(X) 行の実行回数を答えよ。
7. 配列 C を algo4 でソートするとき、(Y) 行の実行回数を答えよ。
8. algo4 が algo3 より配列要素の入れ換え回数を減らすために用いている工夫を述べよ。

题目描述

给出四个用 C 语言实现的升序排序函数 algo1 至 algo4（完整代码见上文），其中 swap 用于交换两个按引用传入的变量。待排序数组为

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. 分别用 algo1 排序数组 A、B，写出第 8 次执行 swap 后的数组状态。
3. 对满足 $d_k>d_{k+1}$（$0\le k\le n-2$）的数组执行 algo1，求 swap 的执行次数。
4. 填写 algo2 中的空格 (b)。
5. 从算法机制说明为什么 algo2 的 swap 次数少于 algo1。
6. 用 algo3 排序数组 C 时，求标记为 (X) 的语句执行次数。
7. 用 algo4 排序数组 C 时，求标记为 (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)

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

$$\boxed{\frac{n(n-1)}2}$$

である。

(4)

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

(b) = d[k]

である。

(5)

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

(6)

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

$$\boxed{8\text{ 回}}$$

である。

(7)

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

ギャップ $g$	(Y) の回数	処理後の配列
4	5	1 4 3 2 5 8 7 6 9
2	2	1 2 3 4 5 6 7 8 9
1	0	1 2 3 4 5 6 7 8 9

したがって合計は

$$\boxed{5+2+0=7\text{ 回}}$$

である。

(8)

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