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

Author

kainoj

Description

Consider the Java program below to sort an array in an ascending order. , , and are positive integers, and is an array of nonnegative integers where for all .
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 -th position in the list lst (the position number starts from 0).
• lst.insert(i, x): inserts to the list lst at the -th position.

is an array of size , 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 .

(2) Let be the number of times the line is executed. Answer the largest value of in terms of and . Also, answer the expected value of in terms of and , assuming that is distributed independently uniformly randomly over the set . Suppose that for this question.

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

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

Kai

Setting of the problem: we got element and 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 will be executed:

times. Note that it has to be an increasing order, because items are being inserted at the beginning of a bucket. If we wanna do evil, we must make every item traverse the whole bucket, until the end. It is possible when every inserted item is bigger than any element in the bucket, that is, input sequence is of increasing order.

(3)

Let denote size of -th bucket. Line is de facto an insertion sort, which means that -th~bucket will be sorted in . Total running time will be to:

Taking expectation:

What is ? Note that, by definition for any random variable . Let be an indicator random variable:

Since we have buckets and every of them is equally likely, probability of "going to bucket " is . Thus, expectation of is:

We can also notice, that, is just a binomial random variable with expectation and variance . Here a trial is mapping an item into bucket, and the success is placing it into -th bucket. There are trials and probability of success if .

Finally:

The following contribute to total expected running time:

• finding a bucket for each element
• sorting each bucket,
• for each bucket, getting its content:

Total running time:

When is , then we get expected running time. When is , then the running time is .

(4)

• BS is stable, QS isn't
• BS isn't in-place, QS is
• BS runs expected, QS is
• BS has upper limit on keys, QS hasn't