2 クイックソート

平成16年度横浜国立大学工学部編入試験に出題された問題である。

2.1 問題

$N$個の要素を持つ整数型配列a[]が与えられているとする。このとき、a[0]〜 a[N-1]の要素を昇順に整列するプログラムについて以下の問いに答えなさい。

なお、/*1*/の行の割算は整数の割算(小数点以下切捨て)である。

[問1]

下記プログラムが目標どおり動作するように 〜 を埋めな さい。ただし、下記プログラムにおいてNの値は8である。

[問2]

完成したプログラムの出力結果を示しなさい。ただし、複数行の出力が印 刷される場合には、各行の時間順序も正しくないといけません。

[問3]

このアルゴリズムでは配列a[]の要素の比較回数(/*2*/および /*3*/の関係演算子の実行回数)は、一般にどれくらいと見積もられる か。$N$を用いた式を用いて簡潔に説明しなさい。

#include <stdio.h>
#define N 8

int a[N]={3,1,5,8,2,6,7,4};

void sort(int [], int, int);
void swap(int [], int, int);

void main(void){
  sort(a, 0, N-1);
}


void sort(int a[], int L, int R){
  int i, j, part;

  i = L;
  j = R;

  part = a[(L+R)/2];

  do{
    while(a[i] < part) i++;
    while(part < a[j]) j--;

    if(i <= j){
      swap(a, i, j);
      i++;
      j--;
    }
  }while(i <= j);

if(L < j)sort(a, , );
if(i < R)sort(a, , );

}


void swap(int a[], int x, int y){
  int temp;

  temp = a[x];
  a[x] = a[y];
  a[y] = temp;

  printf("(%d, %d)\n", x, y);
}

2.2 解答

クイックソートに関する出題である。クイックソートが理解できていれば解ける はずである。問3は少し難しく、一度学習していないと解けないだろう。それでは、解答 を以下に示す。

[問1]

クイックソートのプログラムにするためには、A〜Dは以下の通りにする必 要がある。
L
j
i
R

[問2]

プログラムの出力は以下の通り。

(3, 7)
(2, 4)
(3, 3)
(0, 1)
(1, 2)
(5, 5)

[問3]

sort()関数が最初に呼び出されたときの比較(/*2*/と /*3*/)の実行回数は、$N$あるいは$N+1$回である。平均で、 $(2N+1)/2$回の比較が行われる。そして、再帰呼び出しにより、$\alpha$ 個と$\beta$個の場合のsort()が呼び出されることになる。$N$個の時 のトータルの比較回数を$a_N$として、これらの関係は、

$$a_N=\frac{2N+1}{2}+a_\alpha+a_\beta$$ (1)

となる。もちろん、$\alpha$と$\beta$は、$1$〜$N-1$の値を取りうる。そ して、a[]に格納されている値がランダムであれば、同 じ確率で$1$〜$N-1$の値をとる。さらに、$\alpha$と$\beta$の和は$N$に なることはクイックソートのアルゴリズムから自明である。したがって、 $a_N$の期待値は、

$$a_N =\frac{2N+1}{2}+\frac{1}{N-1}\left(a_1+a_2+a_3+\cdots+a_{N-1} +a_{N-1}+a_{N-2}+a_{N-3}+\cdots+a_1\right)$$

$$=\frac{2N+1}{2}+\frac{2}{N-1}\sum_{k=1}^{N-1}a_k$$ (2)

となる。この漸化式から、$a_N$を求めることになるが、計算は結構大変で ある。まず、式(2)を

$$(N-1)a_N=\frac{(2N+1)(N-1)}{2}+2\sum_{k=1}^{N-1}a_k$$ (3)

と変形しておく。つぎに、この式の$N$を$N-1$にした場合の式

$$(N-2)a_{N-1}=\frac{(2N-1)(N-2)}{2}+2\sum_{k=1}^{N-2}a_k$$ (4)

を利用する。式(3)から式(4)の辺々を差 し引いて整理すると、

$$(N-1)a_N-(N-2)a_{N-1} = \frac{1}{2}\left[(2N+1)(N-1)-(2N-1)(N-2)\right]+2a_{N-1}$$ (5)

となる。さらに、整理を進めると

$$2(N-1)a_N-2Na_{N-1} =4N-3$$ (6)

となる。両辺を、$(N-1)N$で割ると、

$$\frac{2a_N}{N}-\frac{2a_{N-1}}{N-1} =\frac{4N-3}{(N-1)N}$$

$$=\frac{3}{N}+\frac{1}{N-1}$$ (7)

となる。ここで、$2a_N/N$を$b_N$と置くと、

$$b_N-b_{N-1}=\frac{3}{N}+\frac{1}{N-1}$$ (8)

となり、階差数列を用いて容易に計算できる。すなわち、

$$b_N=b_2+\sum_{k=3}^N\left(\frac{3}{k}+\frac{1}{k-1}\right)$$ (9)

である。$a_2=2$より、$b_2=2$となるので、

$$b_N =2+3\sum_{k=3}^N\frac{1}{k}+\sum_{k=3}^N\frac{1}{k-1}$$

$$=2+3\left(\sum_{k=1}^N\frac{1}{k}-1-\frac{1}{2}\right)+ \left(\sum_{k=1}^N\frac{1}{k}-1-\frac{1}{N}\right)$$

$$=-\frac{7}{2}-\frac{1}{N}+4\sum_{k=1}^N\frac{1}{k}$$ (10)

となる。ここで、$N$が大きい場合、 $\sum_{k=1}^N\frac{1}{k}$は $\log_eN+\gamma$に近づくことが知られている²。$\gamma$はオイラー数と言われる定数で、その値は 0.577$\cdots$である。したがって、$N$が大きい場合、

$$b_N\simeq-\frac{7}{2}-\frac{1}{N}+4(\log_eN+\gamma)$$ (11)

となる。右辺の$\log_eN$は他の項に比べて大きな値を取る³。したがっ て、

$$b_N\simeq 4\log_eN$$ (12)

となる。$b_N$の定義から、

$$a_N \simeq 2N\log_eN$$ (13)

となる。

$a_N$はa[]の要素の比較回数を表す。したがって、$N$が大 きい場合の比較回数は、$2N\log_eN$となる。

ホームページ: Yamamoto's laboratory
著者: 山本昌志