東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年2月実施 問題2

标签：

• Tokyo-University
• Bucket-Sort

Author

kainoj, 祭音Myyura

Description

Consider the Java program below to sort an array $A$ in an ascending order. $M$, $N$, and $K$ are positive integers, and $A$ is an array of $N$ nonnegative integers where $0 \leq A[i] < M$ for all $i \in \{0, \dots, N-1\}$.
In this program, list is a class of an integer list with the following methods:

• lst.size(): returns the number of elements in the list lst.
• lst.get(i): returns the element at the $i$-th position in the list lst (the position number starts from 0).
• lst.insert(i, x): inserts $x$ to the list lst at the $i$-th position.

$B$ is an array of size $K$, whose elements are all initialized to empty lists. Suppose that the execution time of each of the above methods is constant. You can ignore overflow errors.

void mysort(int M, int N, int K, int[] A, list[] B) {
    for (int i = 0; i < N; i++) {
        int m = A[i] * K / M;
        int j = 0;
        for (; j < B[m].size(); j++) {
            if (A[i] <= B[m].get(j)) {
                break;
            }
        }
        B[m].insert(j, A[i]);
    }
    int i = 0;
    for (int m = 0; m < K; m++) {
        for (int j = 0; j < B[m].size(); j++) {
            A[i] = [ blank X ];
            i = i + 1;
        }
    }
}

Answer the following questions:

(1) Answer an appropriate expression to fill the blank $\boxed{\ \ X\ \ }$.

(2) Let $C$ be the number of times the line $6$ is executed. Answer the largest value of $C$ in terms of $N$ and $K$. Also, answer the expected value of $C$ in terms of $N$ and $K$, assuming that $A[i]$ is distributed independently uniformly randomly over the set $\{0, \ldots, M-1\}$. Suppose that $K \ll M$ for this question.

(3) Explain how the expected running time of this program varies when $K$ changes, assuming that $A[i]$ is distributed independently uniformly randomly.

(4) Discuss advantages and disadvantages of this algorithm in comparison to the quicksort algorithm.

题目描述

题中 Java 程序用于将数组 $A$ 按升序排序。$M,N,K$ 为正整数， $A$ 含 $N$ 个非负整数，且对所有 $i\in\{0,\ldots,N-1\}$ 均有 $0\le A[i]<M$。list 是整数列表类，size() 返回元素数， get(i) 返回从 $0$ 开始编号的第 $i$ 个元素，insert(i,x) 在第 $i$ 个位置插入 $x$；这些方法均视为常数时间。$B$ 是长度为 $K$ 的数组，每个元素初始为空列表。 忽略整数溢出。

程序先按

$$m=A[i]K/M$$

把每个元素分配到桶 $B[m]$，并通过顺序扫描把它插入桶内的有序位置；随后按桶号从小到大把各桶元素写回 $A$。回答下列问题。

（1）给出填入空白 $\boxed{X}$ 的合适表达式，使程序正确写回排序结果。

（2）令 $C$ 为程序第 6 行的执行次数。用 $N,K$ 表示 $C$ 的最大值；再假设每个 $A[i]$ 独立地在 $\{0,\ldots,M-1\}$ 上均匀分布，并假设 $K\ll M$，求 $C$ 的期望。

（3）在上述独立均匀分布假设下，说明程序的期望运行时间如何随 $K$ 改变。

（4）与快速排序相比，讨论该算法的优点和缺点。

Kai

Setting of the problem: we got $N$ element and $K$ buckets.

(1)

B[m].get(j)

(2)

The input sequence might be in an increasing order and all elements might fall into one bucket. Thus, line $6$ will be executed:

$$C = 0 + 1 + \cdots + (N-1) = \frac{N(N-1)}{2}$$

times. The input must be increasing because elements are inserted at the beginning of a bucket when they are no larger than its first element. Thus, to make every new element traverse the whole bucket, all elements may be placed in one bucket in increasing order.

For the expectation, let $n_i$ denote the size of bucket $i$, and let

$$X_{i,j}=\begin{cases} 1,&\text{if element $j$ is placed in bucket $i$},\\ 0,&\text{otherwise}. \end{cases}$$

Then $n_i=\sum_{j=1}^N X_{i,j}$. Since each bucket has probability approximately $1/K$ when $K\ll M$,

$$\mathbb E[n_i]=\frac NK, \qquad \operatorname{Var}(n_i)=N\frac1K\left(1-\frac1K\right),$$

and hence

$$\mathbb E[n_i(n_i-1)]=\frac{N(N-1)}{K^2}.$$

Sorted insertion into bucket $i$ takes a number of comparisons of order $n_i(n_i-1)$ in total. Summing over the $K$ buckets gives

$$\mathbb E[C]=\Theta\left( \sum_{i=1}^K\mathbb E[n_i(n_i-1)] \right) =\Theta\left(\frac{N^2}{K}\right).$$

More precisely, let $S_i$ be the number of the first $i$ elements in the bucket of $A[i]$. Ties are negligible, so $S_i\sim\operatorname{Bin}(i,1/K)$. Conditional on $S_i=s$,

$$\mathbb E[C_i\mid S_i=s] =\frac{1+2+\cdots+s+s}{s+1} =\frac{s}{2}+1-\frac1{s+1}.$$

Hence

$$\mathbb E[C] \approx \sum_{i=0}^{N-1}\left[ \frac{i}{2K}+1- \frac{K}{i+1}\left(1-\left(1-\frac1K\right)^{i+1}\right) \right] =\Theta\left(\frac{N^2}{K}\right).$$

(3)

The following operations contribute to the expected running time:

• finding a bucket and inserting each element: $\Theta(N)+\Theta(N^2/K)$;
• scanning the $K$ buckets and writing their $N$ elements back: $\Theta(N+K)$.

Thus

$$\mathbb E[T]=\Theta\left(N+K+\frac{N^2}{K}\right).$$

Increasing $K$ reduces collisions until $K=\Theta(N)$, where the expected time is minimized at $\Theta(N)$. For larger $K$, scanning the empty buckets makes the $\Theta(K)$ term dominant.

(4)

• With $K=\Theta(N)$ and uniformly distributed bounded keys, this algorithm has expected $\Theta(N)$ time, compared with quicksort's expected $\Theta(N\log N)$.
• Its worst-case time is $\Theta(N^2)$, and poor bucket balance degrades its performance.
• It needs $\Theta(N+K)$ auxiliary space and a known bounded key range; quicksort applies to general comparable keys and is usually in-place apart from its recursion stack.
• This implementation is not stable: the test A[i] <= B[m].get(j) inserts a new equal key before earlier equal keys.