大阪大学情報科学研究科情報工学 2010年8月実施必須問題#

Author#

KardeniaPoyu

Description#

配点： (1) 15点, (2) 24点, (3) 24点, (4-1) 13点, (4-2) 12点, (4-3) 12点

図1の ANSI-C 準拠である C 言語のプログラムは、53行目の整数型 (int 型) 配列 (array) dat で与えられる入力に対して、昇順 (ascending order) に整列 (sort) するプログラムである。以下の各問に答えよ。

1
#include <stdio.h>
2
#define MAX 8
3

4
void display(int *arr) {
5
    int i;
6
    for(i=0; i<MAX; i++) printf("%d ", arr[i]);
7
    printf("\n");
8
}
9

10
int arrange(int a, int b, int *arr) {
11
    int left, right, bd, temp;
12
    left=a; right=b; bd=arr[(a+b)/2];
13

14
    while(1) {
15
        while(arr[left]<bd) {
16
            left++; if(left>b) break;
17
        }
18
        while(arr[right]>=bd) {
19
            right--; if(right<a) break;
20
        }
21

22
        if(right<a) {
23
            arr[(a+b)/2]=arr[a]; arr[a]=bd;
24
            return a+1;
25
        } else if(left<=right) {
26
            temp=arr[left];
27
            arr[left]=arr[right]; arr[right]=temp;
28
            left++; right--;
29
        } else {
30
            break;
31
        }
32
    }
33
    return(left);
34
}
35

36
void sort(int a, int b, int *arr) {
37
    int k;
38
    if(b<=a) return;
39
    k=arrange(a, b, arr);
40
    display(arr);
41
    sort(a, k-1, arr);
42
    sort(k, b, arr);
43
}
44

45
int main(void) {
46
    int dat[]={30, 50, 70, 40, 20, 80, 60, 10};
47
    sort(0, MAX-1, dat);
48
    display(dat);
49
    return 0;
50
}

(1) このプログラムで実現されている整列方式 (sorting algorithm) の名称を答えよ。

(2) このプログラムの4行目の display 関数を、1回目に呼び出すときと、3回目に呼び出すときの、配列 dat の内容を記述せよ。

(3) このプログラムは、入力を指定する53行目の配列 dat によって動作が変化する。49行目の sort 関数の呼び出しにおいて、常に k と b が等しくなり、かつ25行目の処理が行われないように、配列 dat を並べ替えよ。

(4) 49行目の sort 関数の呼び出しにおいて、常に k と b が等しくなる配列 dat が与えられたときについて、以下の各小問に答えよ。 (4-1) 配列 dat の要素数を $n$ としたとき、プログラム実行の全体における sort 関数が呼び出される回数を求めよ。 (4-2) このような状況における、このプログラムが示す整列方式の時間計算量 (time complexity) を、整列要素数 $n$ を用いてオーダー表記 (order notation) で答えよ。 (4-3) これは、このプログラムが示す整列方式にとってどのような状況であるか、時間計算量の観点から簡潔に述べよ。

Kai#

(1)#

解答: クイックソート (Quick Sort)

(2)#

解答:

1回目: 30, 10, 20, 40, 70, 80, 60, 50
3回目: 10, 20, 30, 40, 70, 80, 60, 50

解説: arrange 関数は与えられた範囲の中央の要素 arr[(a+b)/2] をピボット (bd) とし、それ未満の要素を左側、それ以上の要素を右側に分割します。

初期状態の配列: 30, 50, 70, 40, 20, 80, 60, 10

1回目の sort(0, 7, dat) 呼び出し時の arrange(0, 7, dat):

ピボット bd = arr[3] = 40
leftは40未満の要素を探し、rightは40以上の要素を探して交換します。
1回目の交換: arr[1] (50) と arr[7] (10) を交換。配列は 30, 10, 70, 40, 20, 80, 60, 50 となる。
2回目の交換: arr[2] (70) と arr[4] (20) を交換。配列は 30, 10, 20, 40, 70, 80, 60, 50 となる。
この後、leftは3 (40)、rightは2 (20) となりループを終了。leftである k=3 を返します。
ここで1回目の display が呼ばれます。配列は 30, 10, 20, 40, 70, 80, 60, 50。

次に sort(0, 2, dat) が呼ばれます（arrange(0, 2, dat)）:

ピボット bd = arr[1] = 10
right が -1 まで減少し right < a の条件を満たし、25行目で arr[1] と arr[0] の値を操作します。結果的に arr[0] に 10、arr[1] に 30 が入ります。
返り値は k = 1。
ここで2回目の display が呼ばれます。配列は 10, 30, 20, 40, 70, 80, 60, 50。

次に左側 sort(0, 0, dat) が呼ばれて直ちにリターンし、右側 sort(1, 2, dat) が呼ばれます（arrange(1, 2, dat)）:

ピボット bd = arr[1] = 30
left は2 (20)、right は2 (20) で停止し、arr[1] (30) と arr[2] (20) を交換します。
返り値は k = 2。
ここで3回目の display が呼ばれます。配列は 10, 20, 30, 40, 70, 80, 60, 50。

(3)#

解答: 20, 40, 60, 80, 10, 50, 30, 70

解説: k と b が常に等しくなるということは、arrange 関数の返り値である left が常に b になることを意味します。この時、分割後の右側の要素数が1つ（kからbなのでbのみ）、左側の要素数がそれ以外すべてという最も偏った分割が毎回の再帰で発生します。また、25行目が実行されないためには、right < a が真にならない必要があります。これを実現するためには、各再帰ステップにおいて、選択されるピボット arr[(a+b)/2] が、その部分配列 arr[a...b] における最大値であり、交換によって arr[b] の位置に移動し、残りの要素が左側に寄るようにする必要があります。ソート済みの状態から逆順に操作を辿ることで、この特定の入力配列を構築できます。

(4-1)#

解答: $2n - 1$ 回

解説: k=b が常に成り立つため、部分配列のサイズ $m$ に対する sort(a, b) は、サイズ $m-1$ の sort(a, b-1) と、サイズ $1$ の sort(b, b) を呼び出します。サイズ $n$ の最初の呼び出しから始まり、サイズ $n-1, n-2, \dots, 1$ と再帰が深くなります。各ステップで、サイズ1の部分問題（ベースケースで直ちに終了）が1回呼ばれます。したがって、sort の呼び出し回数は、サイズが減っていく主流の呼び出しが $n$ 回、そこから派生するサイズ1の呼び出しが $n-1$ 回となり、合計で $n + (n-1) = 2n-1$ 回となります。