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

Author

祭音Myyura

Description

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

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

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

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 個のデータを整列するとき、クイックソートの平均計算量は であるが、最悪の場合は となる。 設問2の修正したプログラムで 個の整数を入力として整列するとき、この最悪の場合に相当する入力の例と、それがクイックソートによって整列される過程を示せ。

Kai

設問1

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

設問2

以下の部分によって、

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

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

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

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

を整列する過程：

設問3