IS CS-2022S-02

题目来源：Problem 2 日期：2024-07-02 题目主题：CS-算法-递归排序

具体题目

The following program written in C language defines a function mysort(a, i, j), which sorts an integer array a from a[i] to a[j-1] in ascending order (where $i<j$). The function multfrac(k, l, m) used in the program returns the least integer that is greater than or equal to $k\times \frac{l}{m}$, when $k$, $l$, and $m$ are positive integers. Assume that $w$, $x$, $y$, and $z$ are positive integer constants. Assume also that integer operations never overflow.

int multfrac(int k, int l, int m) {
    return (k * l + (m-1)) / m;
}
 
void compare_swap(int *p, int *q) {
    if (*p > *q) {
        int tmp = *p;
        *p = *q;
        *q = tmp;
    }
}
 
void mysort(int a[], int i, int j) {
    int k = j - i;
    if (k < 4) {
        // X
    }
    else {
        mysort(a, i, i + multfrac(k, x, w));
        mysort(a, j - multfrac(k, y, w), j);
        mysort(a, i, i + multfrac(k, z, w));
    }
}

Answer the following questions.

1. Answer appropriate code to fill the blank X when $(w,x,y,z)$ is $(4,3,3,3)$. You are not allowed to use a function call except for compare_swap. The code may consist of multiple lines.

2. Let $T(n)$ denote the number of times that the code fragment X is executed while mysort(a, 0, n) is called. Give the order of $T(n)$ on $n$ when $(w,x,y,z)$ is $(4,3,3,3)$.

3. Answer whether or not mysort always works correctly for each case where $(w,x,y,z)$ is $(4,2,3,3)$, $(4,3,2,3)$, $(4,3,3,2)$, and $(4,2,3,2)$.

4. Give a necessary and sufficient condition on $w$, $x$, $y$, and $z$ that guarantees mysort to always work correctly.

正确解答

Question 1

To fill the blank X for $(w,x,y,z)=(4,3,3,3)$, we need to handle the cases where the segment length is less than 4. Given that $k=j-i<4$, we can have the following cases for $k=3$, $k=2$, and $k=1$. Since we are only allowed to use the compare_swap function, the code for X is as follows:

if (k == 3) {
    compare_swap(&a[i], &a[i+1]);
    compare_swap(&a[i+1], &a[i+2]);
    compare_swap(&a[i], &a[i+1]);
} else if (k == 2) {
    compare_swap(&a[i], &a[i+1]);
} else {
    // Do nothing if k == 1, as a single element is already sorted.
}

Question 2

Let $T(n)$ denote the number of times the code fragment X is executed when mysort(a, 0, n) is called. For $(w,x,y,z)=(4,3,3,3)$, the recursion splits the array into smaller parts until each segment is less than 4 elements long.

For large $n$, the number of segments of length less than 4 will dominate. Each level of recursion will split the problem into smaller subproblems, each reducing the size of the segment by a fraction. Specifically, the recurrence relation can be approximated by:

$$T(n)\approx 3T\left(\frac{3n}{4}\right)+O(1)$$

Using the Master Theorem for divide-and-conquer recurrences, we find that this recursion falls into case 1 (where $a>b^c$ for $a=3$ and $b^c=(\frac{4}{3}{)}^1$). Thus, the solution to this recurrence is:

$$T(n)=O(n^{{\log }_{\frac{4}{3}}3})=O(n^{1.2619})$$

Question 3

Example Analysis

Let’s provide a complete analysis for the given problem, including the appropriate configurations and the necessary conditions for the sorting algorithm to work correctly. We will use the example where the array is initially sorted in descending order and analyze each step.

Example Configuration: $(w,x,y,z)=(4,2,3,3)$

Recursive Steps Analysis

1. Initial Array:

   DCBA
   

2. First Recursive Call: mysort(a, i, i + multfrac(k, 2, 4))

   • Handles the range: $[i,i+\lceil \frac{k\cdot 2}{4}\rceil )=[i,i+\lceil \frac{k}{2}\rceil )$
   • Array after sorting: $C^{\prime }{D}^{\prime }|BA$

3. Second Recursive Call: mysort(a, j - multfrac(k, 3, 4), j)

   • Handles the range: $[j-\lceil \frac{3k}{4}\rceil ,j)$
   • Array after sorting: $C^{\prime }|A^{\prime }|B|D^{\prime }$

4. Third Recursive Call: mysort(a, i, i + multfrac(k, 3, 4))

   • Handles the range: $[i,i+\lceil \frac{3k}{4}\rceil )$

   • Array after sorting: $A^{\prime }|B^{\prime }|C^{\prime }|D^{\prime }$

Observation

• The final array is sorted correctly as A'B'C'D'.

Detailed Analysis for Different Configurations

Let’s analyze each configuration with an example where the array is initially sorted in descending order: DCBA.

Configuration: $(4,2,3,3)$

1. First Recursive Call: mysort(a, i, i + \lceil \frac{k}{2} \rceil)

   • Array: $DC|BA$
   • After sorting: $C^{\prime }{D}^{\prime }|BA$

2. Second Recursive Call: mysort(a, j - \lceil \frac{3k}{4} \rceil, j)

   • Array: $C^{\prime }{D}^{\prime }|B|A$
   • After sorting: $C^{\prime }|A^{\prime }|B|D^{\prime }$

3. Third Recursive Call: mysort(a, i, i + \lceil \frac{3k}{4} \rceil)

   • Array: $C^{\prime }{A}^{\prime }|B|D^{\prime }$
   • After sorting: $A^{\prime }|B^{\prime }|C^{\prime }|D^{\prime }$

• Observation: The final array is sorted correctly as A'B'C'D'.

Configuration: $(4,3,2,3)$

1. First Recursive Call: mysort(a, i, i + \lceil \frac{3k}{4} \rceil)

   • Array: $D|C|BA$
   • After sorting: $B^{\prime }{C}^{\prime }{D}^{\prime }|A$

2. Second Recursive Call: mysort(a, j - \lceil \frac{k}{2} \rceil, j)

   • Array: $B^{\prime }{C}^{\prime }|A|D^{\prime }$
   • After sorting: $B^{\prime }|A^{\prime }|C^{\prime }|D^{\prime }$

3. Third Recursive Call: mysort(a, i, i + \lceil \frac{3k}{4} \rceil)

   • Array: $B^{\prime }|A^{\prime }|C^{\prime }|D^{\prime }$
   • After sorting: $A’ | B’ | C’ | D’`

• Observation: The final array is sorted correctly as A'B'C'D'.

Configuration: $(4,3,3,2)$

1. First Recursive Call: mysort(a, i, i + \lceil \frac{3k}{4} \rceil)

   • Array: $D|C|BA$
   • After sorting: $B^{\prime }{C}^{\prime }{D}^{\prime }|A$

2. Second Recursive Call: mysort(a, j - \lceil \frac{3k}{4} \rceil, j)

   • Array: $B^{\prime }{C}^{\prime }{D}^{\prime }|A$
   • After sorting: $B^{\prime }{C}^{\prime }|A^{\prime }|D^{\prime }$

3. Third Recursive Call: mysort(a, i, i + \lceil \frac{k}{2} \rceil)

   • Array: $B^{\prime }{C}^{\prime }|A^{\prime }|D^{\prime }$
   • After sorting: $A’ | B’ | C’ | D’`

• Observation: The final array is sorted correctly as A'B'C'D'.

Configuration: $(4,2,3,2)$

1. First Recursive Call: mysort(a, i, i + \lceil \frac{k}{2} \rceil)

   • Array: $DC|BA$
   • After sorting: $C^{\prime }{D}^{\prime }|BA$

2. Second Recursive Call: mysort(a, j - \lceil \frac{3k}{4} \rceil, j)

   • Array: $C^{\prime }{D}^{\prime }|B|A$
   • After sorting: $C^{\prime }|A^{\prime }|B|D^{\prime }$

3. Third Recursive Call: mysort(a, i, i + \lceil \frac{k}{2} \rceil)

   • Array: $C^{\prime }|A^{\prime }|B|D^{\prime }$
   • After sorting: $A^{\prime }|C^{\prime }|B^{\prime }|D^{\prime }$

• Observation: The final array is not correctly sorted. The third call does not ensure sufficient overlap to sort the entire array.

For mysort to work correctly, the recursive calls must ensure that the entire segment is eventually sorted. This requires careful overlapping of the segments in each recursive step.

• $(w,x,y,z)=(4,2,3,3)$:

  • The first call covers $\left[i,i+\lceil \frac{k}{2}\rceil \right)$.
  • The second call covers $\left[j-\lceil \frac{3k}{4}\rceil ,j\right)$.
  • The third call covers $\left[i,i+\lceil \frac{3k}{4}\rceil \right)$.

  This configuration ensures sufficient overlap, so it works correctly.

• $(w,x,y,z)=(4,3,2,3)$:

  • The first call covers $\left[i,i+\lceil \frac{3k}{4}\rceil \right)$.
  • The second call covers $\left[j-\lceil \frac{k}{2}\rceil ,j\right)$.
  • The third call covers $\left[i,i+\lceil \frac{3k}{4}\rceil \right)$.

  This configuration ensures sufficient overlap, so it works correctly.

• $(w,x,y,z)=(4,3,3,2)$:

  • The first call covers $\left[i,i+\lceil \frac{3k}{4}\rceil \right)$.
  • The second call covers $\left[j-\lceil \frac{3k}{4}\rceil ,j\right)$.
  • The third call covers $\left[i,i+\lceil \frac{k}{2}\rceil \right)$.

  This configuration ensures sufficient overlap, so it works correctly.

• $(w,x,y,z)=(4,2,3,2)$:

  • The first call covers $\left[i,i+\lceil \frac{k}{2}\rceil \right)$.
  • The second call covers $\left[j-\lceil \frac{3k}{4}\rceil ,j\right)$.
  • The third call covers $\left[i,i+\lceil \frac{k}{2}\rceil \right)$.

  This configuration does not ensure sufficient overlap, so it does not work correctly.

Question 4

Key Insights

To guarantee that mysort always works correctly, the recursive calls must ensure that all elements in the array are covered and sorted properly. This requires:

1. Coverage: The recursive calls must cover all elements in the array.
2. Overlap: There must be sufficient overlap to ensure that elements are sorted correctly and their positions are fixed in each step.
3. Problem Size Reduction: Each recursive call must reduce the problem size to ensure termination.

Critical Observation

After the first two recursive calls:

• The largest $\lceil \frac{x+y}{w}-1\rceil$ elements must be correctly positioned at the end of the array.

Thus, for the third call to ensure full sorting:

• The third call must cover the remaining $\lceil 1-\left(\frac{x+y}{w}-1\right)\rceil$ elements.

Necessary and Sufficient Conditions

Based on our analysis of the multfrac function and the requirements for correct sorting, we can derive the following necessary and sufficient conditions:

1. Problem Size Reduction Condition:

   $\max \left(\frac{x}{w},\frac{y}{w},\frac{z}{w}\right)<\frac{3w+1}{4w}$

   This condition, derived from the analysis of the multfrac function, guarantees that each recursive call reduces the problem size for any $k\ge 4$.

2. Overlap Condition for Third Call:

   $\frac{z}{w}\ge 2-\frac{x+y}{w}$

   This ensures that the third call covers all elements not fully sorted by the first two calls.

3. Integer Parameter Conditions:

   $0<x,y,z<w$

   $w,x,y,z\in {\mathbb{Z}}^{+}$

   These conditions ensure that all parameters are positive integers and that x, y, and z are strictly less than w.

Complete Necessary and Sufficient Condition

Combining all these conditions, the complete necessary and sufficient condition for mysort to work correctly is:

$$\{\begin{array}{l}\max \left(x,y,z\right)<\frac{3w+1}{4}\\ x+y+z\ge 2w\\ 0<x,y,z<w\\ w,x,y,z\in {\mathbb{Z}}^{+}\end{array}$$

Explanation

1. The first condition ensures proper coverage of the array by the first two recursive calls.
2. The second condition, derived from the multfrac function analysis, guarantees problem size reduction in each recursive call, preventing infinite recursion.
3. The third condition ensures that the third call covers any elements not fully sorted by the first two calls.
4. The fourth and fifth conditions ensure that all parameters are valid positive integers, with x, y, and z being strictly less than w.

These conditions together guarantee that mysort will correctly sort the array and terminate for any input size.

知识点

递归分治算法排序算法

解题技巧和信息

1. 递归调用的正确性依赖于覆盖和重叠。每个递归调用必须覆盖整个数组段，确保所有元素最终被排序。
2. 主定理（Master Theorem） 是解决递归关系的有力工具，特别是在分析算法复杂度时。
3. 对于分治算法，理解各个部分的覆盖范围和重叠部分对于正确性和效率的保证非常重要。

重点词汇

recursive call 递归调用

coverage 覆盖

overlap 重叠

Master Theorem 主定理

complexity analysis 复杂度分析

参考资料

1. Introduction to Algorithms, Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Chap. 4.
2. Algorithms, Fourth Edition, by Robert Sedgewick and Kevin Wayne, Chap. 2.