東京大学 新領域創成科学研究科 メディカル情報生命専攻 2016年8月実施 問題9

Author

zephyr

Description

Suppose that is an array with distinct integers. The quicksort algorithm for sorting in the ascending order has the following three steps.

A) Select and remove an element from . Call a pivot.

B) Divide into arrays and such that for and for .

C) Sort and in the ascending order using quicksort, and return the concatenation of , , and .

Answer the following questions.

(1) How would you implement Step B in quicksort?

(2) In Step A, if we always set the first element in to pivot , show an input array that the algorithm sorts in worst-case time, and prove this property.

(3) In Step A, if we select a position in at random and set the element at the position to pivot , prove that the expected time complexity is for an arbitrary input array.

(4) Design an algorithm that calculates the -th smallest element in in expected time, and prove this property.

---

假设 是一个包含 个不同整数的数组。用于升序排列 的快速排序算法有以下三个步骤。

A) 从 中选择并移除一个元素 。称 为枢轴。

B) 将 分成数组 和 ，使得 对于所有 ，并且 对于所有 。

C) 使用快速排序按升序排列 和 ，并返回 ， 和 的连接。

回答以下问题。

(1) 你将如何在快速排序中实现步骤 B？

(2) 在步骤 A 中，如果我们总是将 的第一个元素设置为枢轴 ，展示一个输入数组，使算法在 最坏情况下进行排序，并证明这一性质。

(3) 在步骤 A 中，如果我们在 中随机选择一个位置并将该位置的元素设置为枢轴 ，证明对于任意输入数组，预期时间复杂度为 。

(4) 设计一个算法，在 预期时间内计算 中的第 小元素，并证明这一性质。

Kai

(1)

To implement Step B, we need to partition the array around the pivot element . Here is a common way to do it, known as the Lomuto partition scheme:

1. Initialize an index 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

(2)

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:

Proof of Time Complexity:

1. In the first call, the pivot is the smallest element (1), and the array is divided into and .
2. In the second call, the pivot is the smallest element in (2), and the array is divided into and .
3. This process continues, making comparisons in the first step, in the second step, and so on.

The total number of comparisons is:

(3)

To rigorously prove that the expected time complexity of Quicksort with a random pivot selection is , we will employ probabilistic analysis.

Definitions and Assumptions

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

Key Observations

1. When a pivot is chosen, it partitions the array into two subarrays and . The sizes of and depend on the position of in the sorted array.

2. If the pivot is the -th smallest element, will have elements and will have elements.

3. The number of comparisons required to partition the array around the pivot is .

Expected Comparisons

We aim to find , the expected number of comparisons for an array of size .

The recurrence relation for is:

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

The expected number of comparisons is:

Taking Expectation

Since the pivot is chosen randomly, the expected sizes of and are uniformly distributed:

This simplifies to:

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 is bounded by some function . We hypothesize that . Let's test this hypothesis by substituting it into the recurrence relation:

Assume for some constant . Then,

We can approximate the sum using integral approximation:

Compute the integral:

Evaluate the integral from to :

At :

At :

So the integral result is approximately:

Simplifying this, we get:

Thus,

Substitute this back into the recurrence relation:

Simplify:

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

Thus, the expected number of comparisons for Quicksort with a random pivot selection is .

(4)

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 randomly.
2. Partition the array into and as described in Step B.
3. If the size of is , then is the -th smallest element.
4. If the size of is greater than , recurse into .
5. Otherwise, recurse into with the adjusted 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 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:

This solves to using the Master Theorem or similar analysis.

Knowledge

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

重点词汇

• 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)