東京大学 工学系研究科 電気系工学専攻 2024年8月実施 問題4 情報工学II

标签：

• Tokyo-University
• Quick-Sort

Author

adj-matrix

Description

I.

TODO

II.

Consider the following algorithm $f(X)$, which overwrites an input array $X = (x_1, x_2, \cdots, x_n)$ of $n$ distinct non-negative integers to sort its components in ascending order:

1. for $n = 0$ or $n = 1$, do nothing.
2. for $n = 2$, do nothing if $x_1 < x_2$, and overwrite $X$ as $X = (x_2, x_1)$, otherwise.
3. for $n > 2$, select an element $p$ of $X$ by using a function $h(X)$ as $p = h(X)$. Let $X_1$ be an array consisting of all the elements in $X$ being smaller than $p$, and $X_2$ be an array consisting of all the elements in $X$ being greater than $p$. Overwrite $X$ as $X = (X_1, p, X_2)$. Then, recursively apply $f$ to the subarrays $X_1$ and $X_2$ in $X$ as $f(X_1)$ and $f(X_2)$, respectively.

Answer the following questions.

(1) Fig. 8 exemplifies the operation of $f$ for an array $X = (6,9,3,5,1,7)$ when $h(X) = x_1$ and the order of the elements in $X_1$ and $X_2$ inherits their order in $X$. Draw the operation of $f$ for $X = (6,8,4,5,2,3,1,9,7)$ by following the diagram in Fig. 8.

(2) Suppose that an array $X$ contains each integer from 1 to 9, once each. Also, assume that $h(X) = x_1$ and the order of the elements in $X_1$ and $X_2$ inherits their order in $X$. Obtain the array $X_{\max}$ that maximizes the number of recursive calls of $f(X)$ and has the largest value evaluated as a 9-digit integer. Also obtain the array $X_{\min}$ that minimizes the number of recursive calls of $f(X)$ and has the largest value evaluated as a 9-digit integer. Note that the value of $X = (1,2,3,4,5,6,7,8,9)$ evaluated as a 9-digit integer is 123456789.

(3) Assume that $h(X) = x_1$. For an array $X$ with length $n$, obtain the order of worst-case time complexity by supplementing the intermediate steps of its derivation. In the derivation, evaluate the order of the time complexity in terms of comparisons, while ignoring the complexity of the other operations.

(4) Program 1 is an implementation of the algorithm $f(X)$ in the C programming language. Describe the codes that should be in the blanks, [A], [B], and [C].

(5) Suppose that $h(X)$ is a function that returns an element $p$ selected from $X$ uniformly and randomly. Answer the order of the average time complexity of $f(X)$ as a function of $n$. In addition, describe its reason in detail.

Fig. 8

        (6,9,3,5,1,7)
              |
   (3,5,1) -- 6 - (9,7)
      |       |     |
(1) - 3 - (5) |   (7,9)
 |____|____|  |     |
      |       |     |
   (1,3,5) -- 6 - (7,9)
              |
        (1,3,5,6,7,9)

/* Program1 */
void swap(int X[], int i, int j){
    int tmp = X[i]; X[i] = X[j]; X[j] = tmp;
}
int partition (int X[], int left, int right) {
    int pivot = X[left];
    int i = right;
    for (int j = right; j >= left+1; j--) {
        if (X[j] >= pivot) {
            [A]
            i--;
        }
    }
    [B]
    return i;
}
void f(int X[], int left, int right) {
    if (left < right) {
        int pivotpos = partition(X, left, right);
        [C]
    }
}
int main (void) {
    int X[10] = {9, 6, 1, 7, 2, 3, 4, 5, 0, 8};
    f(X, 0, sizeof(X) / sizeof(X[0]) - 1);
    return 0;
}

Kai

I.

TODO

II.

(1)

             (6,8,4,5,2,3,1,9,7)
                      |
       (4,5,2,3,1) -- 6 -- (8,9,7)
              |       |       |
  (2,3,1) --- 4 - (5) | (7) - 8 - (9)
      |       |    |  |  |____|____|
(1) - 2 - (3) |    |  |       |
 |____|____|  |    |  |    (7,8,9)
      |       |    |  |       |
   (1,2,3)    |    |  |       |
      |_______|____|  |       |
              |       |       |
         (1,2,3,4,5)  |       |
              |_______|_______|
                      |
             (1,2,3,4,5,6,7,8,9)

(2)

The worst case is when the partition is as unbalanced as possible. Since we want the digits at the start of the array to be as large as possible. In addition, each integer from 1 to 9 is one each. Therefore, the worst case is 987654321, i.e. $X_{\max}$.

For $X_{\min}$, we want this case: (from bottom to top)

       (1,2,3,4,5,6,7,8,9)
         _______|_________
        |       |         |
    (1,2,3,4)   5     (6,7,8,9)
   _____|____   |    _____|____
  |     |    |  |   |     |    |
(1,2) - 3 - (4) | (6,7) - 8 - (9)
        |       |         |
    (3,4,2,1) - 5 --- (8,9,7,6)
                |
       (5,8,9,7,6,3,4,2,1)

Therefore, the best and largest case is 589763421.

(Note to readers: The C code provided in the question is unstable; it will swap the Pivot to the middle and swap the elements that were originally at the end to the beginning)

(3)

In the worst case, the time complexity $T(n) = T(n-1) + T(0) + O(n)$

Since $T(0)$ is constant, therefore $T(n) = T(n-1) + cn = cn + c(n-1) + c(n-2) + \dots + c(1) \approx c \frac{n(n+1)}{2}$

i.e. $T(n) = O(n^2)$, i.e. the time complexity is $O(n^2)$

(4)

• A: swap(X, i, j);
• B: swap(X, left, i);
• C: f(X, left, pivotpos-1); f(X, pivotpos+1, right)

(5)

Complexity: $O(n \log n)$

Reason:

On average, the randomly chosen pivots splits the array into two subarrays of roughly proportional sizes. Because balanced or near-balanced splits occur with constant probability, the expected height of the recursion tree becomes logarithmic, i.e. $O(\log n)$. Since the partitioning operation at each level of recursion trees takes $O(n)$ time in total, the total expected time complexity is $O(n) \cdot O(\log n) = O(n \log n)$.

The expected running time $T(n)$ satisfies: $T(n) = O(n) + \frac{1}{n} \sum_{i=0}^{n-1} (T(i) + T(n-1-i))$ i.e. $T(n) = O(n \log n)$