Skip to content

京都大学 情報学研究科 知能情報学専攻 2020年8月実施 情報学基礎 F2-2

Author

祭音Myyura

Description

クイックソートについて以下の設問に答えよ。

設問1 クイックソートの基本的な考え方を \(100\) 文字程度で説明せよ。

設問2 以下は整数列のクイックソートを行うC言語プログラムであるが、正しく動作しない。 \(\{3, 2, 6, 8, 5, 1, 7, 4\}\) を入力とする場合を例に、どこに問題があるかを指摘し、プログラムを修正した上で、この例を整列する過程を示せ。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void quick_sort(int a[], int first, int last)
{
    int i, j, x, t;

    x = a[(first + last) / 2];
    i = first; j = last;
    while (1) {
        while (a[i] <= x) i++;
        while (x <= a[j]) j--;
        if (i >= j) break;
        t = a[i]; a[i] = a[j]; a[j] = t;
        i++; j--;
    }
    if (first < i - 1) quick_sort(a, first, i - 1);
    if (j + 1 < last)  quick_sort(a, j + 1, last);
}

設問3 \(n\) 個のデータを整列するとき、クイックソートの平均計算量は \(O(n\log n)\) であるが、最悪の場合は \(O(n^2)\) となる。 設問2の修正したプログラムで \(8\) 個の整数を入力として整列するとき、この最悪の場合に相当する入力の例と、それがクイックソートによって整列される過程を示せ。

Kai

設問1

クイックソートは、ピボットと呼ばれる値を1つ選び、それを基準としてデータ列を「ピボット未満の要素からなるデータ列」と「ピボット以上の要素からなるデータ列」に二分することを再帰的に行うアルゴリズムである。

設問2

以下の部分によって、

1
2
while (a[i] <= x) i++;
while (x <= a[j]) j--;

軸要素 x に最大値が割り当てられたときに、全ての i について a[i] <= x が成立してしまうゆえ，i の値が配列の要素数を超える。

修正する方法は先ほどのソースコードを以下のように変更する。

1
2
while (a[i] < x) i++;
while (x < a[j]) j--;

\(\{3, 2, 6, 8, 5, 1, 7, 4\}\) を整列する過程：

\[ \{3, 2, 6, 8, 5, 1, 7, 4\} \rightarrow \{3, 2, 6, 4, 5, 1, 7, 8\} \rightarrow \{3, 2, 1, 4, 5, 6 ,7 ,8\}\rightarrow \{1, 2, 3, 4, 5, 6, 7, 8\} \]

設問3

\[ \begin{align} \{2,4,6,8,1,5,3,7\} \rightarrow \{2,4,6,7,1,5,3,8\} \\ \rightarrow \{2,4,6,3,1,5,7,8\} \\ \rightarrow \{2,4,5,3,1,6,7,8\} \\ \rightarrow \{2,4,1,3,5,6,7,8\} \\ \rightarrow \{2,3,1,4,5,6,7,8\} \\ \rightarrow \{2,1,3,4,5,6,7,8\} \\ \rightarrow \{1,2,3,4,5,6,7,8\} \end{align} \]