京都大学 情報学研究科 知能情報学専攻 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の修正したプログラムで 個の整数を入力として整列するとき、この最悪の場合に相当する入力の例と、それがクイックソートによって整列される過程を示せ。
题目描述
关于快速排序回答：
-
用约 100 字说明快速排序的基本思想。
-
下列 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);
} -
快速排序平均复杂度为 ，最坏为 。对第 2 问修正后的程序，给出一个含 8 个整数、会触发最坏情形的输入，并展示排序过程。
考点
- 快速排序分区：识别含等号的扫描条件可能越界或跨过枢轴，修正双指针停止和递归区间。
- 递归过程模拟：逐轮展示枢轴选择、交换和子区间递归后的数组状态。
- 最坏复杂度构造：为“中间元素作枢轴”的具体实现设计每次高度不平衡的划分，说明二次时间来源。
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--;
を整列する過程：