排序演算法 - 練習題¶

Q1. Quick Sort Worst Case 條件 (110)¶

When CAN the worst case of Quicksort occur?

\(C_1\): Quick Sort where leftmost (or rightmost) element is always chosen as pivot
\(C_2\): leftmost element is chosen as pivot and array is already sorted in SAME order
\(C_3\): leftmost element is chosen as pivot and array is already sorted in REVERSE order

| (A) \(C_1\) | (B) \(C_2\) | (C) \(C_1\) and \(C_2\) | (D) \(C_2\) and \(C_3\) |

答案與解析

答案: (D) \(C_2\) and \(C_3\)

解析: - 單純選最左或最右元素當 pivot (\(C_1\)) 不一定會造成 worst case - 只有當陣列已經排序（正序或逆序）且選擇最左/最右元素當 pivot 時，每次 partition 只能分出一個元素 - 這導致遞迴深度達到 \(O(n)\)，總時間複雜度為 \(O(n^2)\)

Q2. 排序演算法選擇 (112)¶

Assuming we have n data points. Among the variant characteristics of the data points, please select the correct descriptions.

(A) If the worst-case running time is the most important, merge sort can be a good choice with \(O(n \log n)\) time.
(B) If the input happens to be sorted already, bubble sort can be a best choice with \(O(n)\) time.
(C) If the input array is in random order and the average sorting time is most important, quick sort can be a good choice with \(O(n \log n)\) time.
(D) If the exchanges of the items in the array are very expensive, selection sort will incur the least "swaps" or "moves".
(E) If the input array consists of integers in the range \(1...n^k\), radix sort with radix n with \(O(k \log n)\) time.

答案與解析

答案: (A)(B)(C)(D)

解析: - (A) 正確: Merge Sort 的 worst case 是 \(O(n \log n)\)，穩定可靠 - (B) 正確: Bubble Sort 在已排序陣列上可以 \(O(n)\) 完成（加上提前終止優化） - (C) 正確: Quick Sort 平均時間複雜度 \(O(n \log n)\)，實務上常數較小 - (D) 正確: Selection Sort 最多只做 \(n-1\) 次交換，適合交換成本高的情況 - (E) 錯誤: Radix Sort 時間應為 \(O(k \cdot n)\)，不是 \(O(k \log n)\)

Q3. N-way Merge Sort 複雜度 (112)¶

In a traditional merge sort, two sorted sub-arrays are combined to form a single, fully sorted array. This is referred to as a 2-way merge. The problem at hand is to extend this concept by merging N sorted arrays of integers, where N and M are given integers representing the number of arrays and the number of integers in each array, respectively. Please choose the correct worst-case time complexity of this N-way merge.

答案與解析

答案: (D) \(O(NM \log N)\)

解析: - N-way merge 使用 Min-Heap 來追蹤每個陣列的最小元素 - Heap 大小為 N（N 個陣列各一個元素） - 總共有 \(NM\) 個元素需要處理 - 每次從 heap 取出最小值並插入新元素：\(O(\log N)\) - 總時間：\(O(NM \log N)\)

Q4. 排序演算法複雜度 (107)¶

For each of the following algorithms, what is the tightest asymptotic upper bound for its runtime complexity?

| (A) \(O(1)\) | (B) \(O(n)\) | (C) \(O(\lg n)\) | (D) \(O(n \lg n)\) | (E) \(O(n^2)\) |

Quick sort for n numbers (worst-case time)
Quick sort for n numbers (expected time)
Bucket sort for n numbers (expected time)

答案與解析

答案: 1. (E) \(O(n^2)\) - Quick Sort worst case 2. (D) \(O(n \lg n)\) - Quick Sort expected/average case 3. (B) \(O(n)\) - Bucket Sort expected case（假設均勻分布）

解析: - Quick Sort 在 pivot 選擇不佳時會退化到 \(O(n^2)\) - Quick Sort 平均情況下是 \(O(n \log n)\) - Bucket Sort 在資料均勻分布時可達 \(O(n)\)

Q5. Merge 演算法比較次數下界 (109)¶

Given two sorted list A and B (in increasing key order), the following recursive algorithm merges A and B into a sorted list C (also in increasing key order).

If either A or B is empty then the result is the other list.
If both A or B are not empty, we compare the keys of the first nodes of A and B, and select the smaller one (denoted as s), and remove it from the list. Then we recursively merge the remaining parts of A and B into a new sorted list C', then we concatenate s with C' into the final sorted list C.

Let \(f(n, m)\) be the minimum number of comparisons of this algorithm, where n and m are the numbers of nodes in A and B respectively. \(f(n, m)\) is?

答案與解析

答案: 1. \(\Omega(n)\) 或 2. \(\Omega(m)\)（取較小者）

解析: - **最少**比較次數發生在其中一個 list 的所有元素都比另一個 list 的第一個元素小 - 例如：A = [1, 2, 3], B = [10, 20] - 只需要比較 min(n, m) 次就能確定順序 - 因此下界是 \(\Omega(\min(n, m))\)

Q6. Merge Sort 比較次數上界 (109)¶

We now use the merge algorithm in the previous question to sort a set of keys. We first make each key a list of a single node. Then we merge the first and the second lists into a sorted list of length two, the third and the fourth lists into a sorted list of length two, and so on. If we start with n keys now we have roughly n/2 sorted list of length two now. We then merge these lists of length two into roughly n/4 sorted list of length four, and so on. Finally we will have a sorted list of length n. Let \(f(n)\) denote the maximum possible total number of comparisons of this algorithm, then \(f(n)\) is? (Note that all the answers are in little-o notation.)

| 1. \(o(n)\) | 2. \(o(n\sqrt{n})\) | 3. \(o(n \log n)\) | 4. \(o(n(\log n)^2)\) | 5. \(o(n^2)\) |

答案與解析

答案: 5. \(o(n^2)\)

解析: - Merge Sort 的比較次數最多為 \(O(n \log n)\) - 題目問的是 little-o，即嚴格小於 - \(O(n \log n)\) 是 \(o(n^2)\) 但不是 \(o(n \log n)\) - 因此答案是 \(o(n^2)\)

注意：這題使用 little-o 記號，表示嚴格漸近小於。

Q7. Quick Sort 特性判斷 (108)¶

Quicksort is a fast and commonly used comparison-based sorting algorithm. Below you can find a version of quicksort algorithm in pseudo code format.

QUICKSORT(A, p, r)
1  if p < r
2      q = PARTITION(A, p, r)
3      QUICKSORT(A, p, q - 1)
4      QUICKSORT(A, q + 1, r)

PARTITION(A, p, r)
1  x = A[r]
2  i = p - 1
3  for j = p to r - 1
4      if A[j] ≤ x
5          i = i + 1
6          exchange A[i] with A[j]
7  exchange A[i + 1] with A[r]
8  return i + 1

True or false:

The output of QUICKSORT() above is a non-increasing sorted sequence.
The QUICKSORT() above is a stable sorting algorithm.
The QUICKSORT() above is an in-place sorting algorithm.

答案與解析

答案: 1. False - 輸出是 non-decreasing（遞增）序列，因為 A[j] ≤ x 把小於等於 pivot 的放前面 2. False - Quick Sort 不是穩定排序，相等元素的相對順序可能改變 3. True - Quick Sort 是 in-place 排序，只需要 \(O(\log n)\) 的遞迴堆疊空間

延伸練習¶

Nav

◀ 排序演算法 | 📚 目錄 | 下一章 ▶