お茶の水女子大学 人間文化創成科学研究科 理学専攻 情報科学コース 2019年2月実施 情報基礎 問題1

标签：

• Ochanomizu-University
• Insertion-Sort

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

次のあるソートを行う C 言語のプログラムを考える。

void sort1(int a[], int n)
{
    int i, j;

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

1. 「ソート」、ならびに「昇順」と「降順」を説明せよ。
2. sort1 の処理内容と振る舞いを説明せよ。
3. 6 5 4 7 3 10 9 を処理するとき、各 $i$ における結果を示せ。
4. sort1 の計算量を示せ。
5. データ1 6 5 4 7 3 10 9 とデータ2 1 2 3 4 5 0 6 のどちらが早く処理されるか、理由とともに答えよ。
6. どのような並びのときに処理時間が短くなるか答えよ。

题目描述

给定一段排序程序：说明排序、升序和降序的含义，解释程序；逐轮写出指定数据的排序过程；分析复杂度；比较两组数据的处理速度，并说明该程序何时最快。

Kai

(1)

ソートとは、データを指定されたキーの大小関係に従って並べ替える処理である。小さいものから大きいものへ並べるのが昇順、大きいものから小さいものへ並べるのが降順である。

(2)

sort1 は昇順の挿入ソートである。反復開始時には a[0] から a[i-1] までが整列済みである。tmp = a[i] を取り出し、tmp より大きい要素を一つずつ右へずらして、空いた位置 a[j] に tmp を挿入する。

(3)

$i$	配列
初期	6 5 4 7 3 10 9
1	5 6 4 7 3 10 9
2	4 5 6 7 3 10 9
3	4 5 6 7 3 10 9
4	3 4 5 6 7 10 9
5	3 4 5 6 7 10 9
6	3 4 5 6 7 9 10

(4)

逆順の場合、比較・移動回数は

$$1+2+\cdots+(n-1)=\frac{n(n-1)}2$$

となる。したがって最悪時間計算量は $\Theta(n^2)$、最良時間計算量は $\Theta(n)$ である。相異なる入力の順列が一様に与えられるとき、平均時間計算量も $\Theta(n^2)$ となる。追加領域は $\Theta(1)$ である。

(5)

データ2の方が早い。 このプログラムにおける要素の右移動回数は、入力列の転倒数に等しい。

データ	キー比較	右移動
データ1	11	8
データ2	10	5

よって、データ2の方が比較も移動も少ない。

(6)

入力が最初から昇順に整列しているときである。この場合、各反復で内側の条件が最初の比較で偽になり、全体は $\Theta(n)$ 時間で終了する。