CBMS-2017-09

题目来源：[[文字版题库/CBMS/2017#Problem 9|2017#Question 9]] 日期：2024-07-29 题目主题：CS-算法-快速排序

Solution

Question 1: Implementing Step B in Quicksort

To implement Step B, we need to partition the array $\mathbf{M}$ around the pivot element $x$. Here is a common way to do it, known as the Lomuto partition scheme:

1. Initialize an index $i$ to track the boundary of elements less than or equal to the pivot.
2. Traverse the array from left to right, comparing each element with the pivot.
3. Swap elements to ensure all elements less than or equal to the pivot are on its left, and all elements greater than the pivot are on its right.

Here is a Python function to achieve this:

def partition(arr, low, high):
    pivot = arr[high]  # Choose the last element as pivot
    i = low - 1  # i: Index of smaller element
 
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1  # Increment index of smaller element
            arr[i], arr[j] = arr[j], arr[i]
            # Swap the current element to teh end of the smaller half of arr
 
    arr[i+1], arr[high] = arr[high], arr[i+1]  # Place pivot in correct position
    return i+1  # Return the partition index

Question 2: Worst-case Time Complexity of Quicksort with First Element as Pivot

If we always select the first element as the pivot, the worst-case scenario occurs when the array is already sorted (either in ascending or descending order).

Example of Worst-case Input:

$$\mathbf{M}=[1,2,3,\dots ,n]$$

Proof of $O(n^2)$ Time Complexity:

1. In the first call, the pivot is the smallest element (1), and the array is divided into ${\mathbf{M}}_1=[]$ and ${\mathbf{M}}_2=[2,3,\dots ,n]$.
2. In the second call, the pivot is the smallest element in ${\mathbf{M}}_2$ (2), and the array is divided into ${\mathbf{M}}_1=[]$ and ${\mathbf{M}}_2=[3,4,\dots ,n]$.
3. This process continues, making $n-1$ comparisons in the first step, $n-2$ in the second step, and so on.

The total number of comparisons is:

$$(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}=O(n^2)$$

Question 3: Expected Time Complexity with Random Pivot Selection

To rigorously prove that the expected time complexity of Quicksort with a random pivot selection is $O(n\log n)$, we will employ probabilistic analysis.

Definitions and Assumptions

• Let $T(n)$ be the expected time complexity of Quicksort on an array of size $n$.
• Each pivot is chosen uniformly at random from the array.
• $C(n)$ is the number of comparisons made by Quicksort on an array of size $n$.

Key Observations

1. When a pivot $x$ is chosen, it partitions the array into two subarrays ${\mathbf{M}}_1$ and ${\mathbf{M}}_2$. The sizes of ${\mathbf{M}}_1$ and ${\mathbf{M}}_2$ depend on the position of $x$ in the sorted array.

2. If the pivot is the $i$-th smallest element, ${\mathbf{M}}_1$ will have $i-1$ elements and ${\mathbf{M}}_2$ will have $n-i$ elements.

3. The number of comparisons required to partition the array around the pivot is $n-1$.

Expected Comparisons

We aim to find $E[C(n)]$, the expected number of comparisons for an array of size $n$.

The recurrence relation for $C(n)$ is:

$C(n)=C(i-1)+C(n-i)+(n-1)$

where $i$ is the position of the pivot in the sorted array, chosen uniformly at random from $1$ to $n$.

The expected number of comparisons is:

$E[C(n)]=E\left[C(i-1)\right]+E\left[C(n-i)\right]+(n-1)$

Taking Expectation

Since the pivot is chosen randomly, the expected sizes of ${\mathbf{M}}_1$ and ${\mathbf{M}}_2$ are uniformly distributed:

$E[C(n)]=\frac{1}{n}{\sum }_{i=1}^n\left(E[C(i-1)]+E[C(n-i)]\right)+(n-1)$

This simplifies to:

$E[C(n)]=\frac{2}{n}{\sum }_{i=0}^{n-1}E[C(i)]+(n-1)$

Solving the Recurrence Relation

To solve the recurrence relation, we will use the concept of telescoping sums and known techniques for analyzing recurrence relations.

First, we need to assume that $T(n)$ is bounded by some function $f(n)$. We hypothesize that $T(n)=O(n\log n)$. Let’s test this hypothesis by substituting it into the recurrence relation:

Assume $T(n)=c\cdot n\log n$ for some constant $c$. Then,

$$T(n)=\frac{2}{n}\sum _{i=0}^{n-1}c\cdot i\log i+(n-1)$$

We can approximate the sum ${\sum }_{i=0}^{n-1}i\log i$ using integral approximation:

$$\sum _{i=0}^{n-1}i\log i\approx {\int }_1^{n}x\log x\mathrm{d}x$$

Compute the integral:

$$\int x\log x\mathrm{d}x=\frac{x^2}{2}\log x-\frac{x^2}{4}+C$$

Evaluate the integral from $1$ to $n$:

$${\int }_1^{n}x\log x\mathrm{d}x={\left[\frac{x^2}{2}\log x-\frac{x^2}{4}\right]}_1^n$$

At $x=n$:

$$\frac{n^2}{2}\log n-\frac{n^2}{4}$$

At $x=1$:

$$\frac{1}{2}\log 1-\frac{1}{4}=-\frac{1}{4}$$

So the integral result is approximately:

$$\frac{n^2}{2}\log n-\frac{n^2}{4}+\frac{1}{4}$$

Simplifying this, we get:

$${\int }_1^{n}x\log x\mathrm{d}x\approx \frac{n^2}{2}\log n-\frac{n^2}{4}$$

Thus,

$$\sum _{i=0}^{n-1}i\log i\approx \frac{n^2}{2}\log n-\frac{n^2}{4}$$

Substitute this back into the recurrence relation:

$$T(n)=\frac{2}{n}\left(\frac{n^2}{2}\log n-\frac{n^2}{4}\right)+(n-1)$$

Simplify:

$$T(n)=n\log n-\frac{n}{2}+(n-1)$$

Since lower-order terms are negligible when considering asymptotic behavior, we get:

$$T(n)=O(n\log n)$$

Thus, the expected number of comparisons $T(n)$ for Quicksort with a random pivot selection is $O(n\log n)$.

Question 4: Algorithm for the $k$-th Smallest Element in $O(n)$ Expected Time

This can be achieved using the Quick-select algorithm, which is similar to Quicksort but only recurses into one partition.

Algorithm:

1. Choose a pivot element $x$ randomly.
2. Partition the array into ${\mathbf{M}}_1$ and ${\mathbf{M}}_2$ as described in Step B.
3. If the size of ${\mathbf{M}}_1$ is $k-1$, then $x$ is the $k$-th smallest element.
4. If the size of ${\mathbf{M}}_1$ is greater than $k-1$, recurse into ${\mathbf{M}}_1$.
5. Otherwise, recurse into ${\mathbf{M}}_2$ with the adjusted $k$ value.

Python Code:

import random
 
def quickselect(arr, low, high, k):
    if low == high:
        return arr[low]
    
    pivot_index = random.randint(low, high)
    pivot_index = partition(arr, low, high)
    
    if k == pivot_index:
        return arr[k]
    elif k < pivot_index:
        return quickselect(arr, low, pivot_index - 1, k)
    else:
        return quickselect(arr, pivot_index + 1, high, k)
 
def find_kth_smallest(arr, k):
    return quickselect(arr, 0, len(arr) - 1, k - 1)

Proof of $O(n)$ Expected Time Complexity:

The Quickselect algorithm has the same recurrence as Randomized Quicksort, but only recurses into one subarray. Hence, the expected time complexity is:

$$T(n)=T\left(\frac{n}{2}\right)+O(n)$$

This solves to $T(n)=O(n)$ using the Master Theorem or similar analysis.

知识点

快速排序时间复杂度分治算法

重点词汇

• Quicksort 快速排序
• Pivot 枢轴
• Partition 分区
• Expected time complexity 期望时间复杂度
• Recurrence relation 递推关系

参考资料

1. Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein, 3rd Edition, Chap. 7 (Quicksort), Chap. 9 (Medians and Order Statistics)