隨機快速排序

習題預習

1. 如何選擇一個pivot元素？
2. 在最壞情況下，Randomized Quicksort的時間複雜度是多少？
3. 如何實現Randomized Quicksort？是否可以使用遞迴？
4. 在實現Randomized Quicksort時，如何確定數據是否已經排好序？
5. Randomized Quicksort是否能夠處理包含相同元素的數據？如果不能，該怎麼處理？

說明知識

Randomized Quicksort是快速排序算法的一種變體，它與原始快速排序算法的區別在於，它使用隨機數來選擇主元素（pivot），從而盡可能避免了最壞情況。在原始的快速排序算法中，選擇的主元素可能會導致分割的子序列不平衡，進而導致算法的時間複雜度退化為O(n2)；而隨機化的選擇主元素，則能夠盡可能保持分割的子序列平衡，從而保證算法的時間複雜度為O(n log n)。

以下是Randomized Quicksort的實現步驟：

1. 選取一個元素作為主元素（pivot），可以隨機選取其中一個元素。
2. 掃瞄整個序列，將比pivot小的元素放到左邊，比pivot大的元素放到右邊，相等的元素放到任意一邊（一般為左邊）。
3. 遞歸排序左右兩個子序列。

以下為Randomized Quicksort的示例代碼：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void randomized_quicksort(int arr[], int left, int right);

int main(void) {
    int arr[] = {3, 5, 2, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    randomized_quicksort(arr, 0, n - 1);
    for(int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

void randomized_quicksort(int arr[], int left, int right) {
    if(left >= right) {
        return;
    }
    int p = rand() % (right - left + 1) + left;
    int pivot = arr[p];
    int i = left;
    int j = right;
    while(i <= j) {
        while(arr[i] < pivot) {
            i++;
        }
        while(arr[j] > pivot) {
            j--;
        }
        if(i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    randomized_quicksort(arr, left, j);
    randomized_quicksort(arr, i, right);
}

在上面的示例代碼中，我們隨機選取一個元素作為主元素（pivot），並通過while循環將比pivot小的元素放到左邊，比pivot大的元素放到右邊，然後遞歸的對左右兩個子序列進行排序。程序的輸出結果為：

1 2 3 4 5

可以看到，我們使用Randomized Quicksort算法成功地將序列從小到大排序了。

彙總重點

以下是Randomized Quicksort的重點：

1. 快速排序是一種具有高效率的排序演算法，而 Randomized Quicksort 是在快速排序的基礎上改進的演算法。

2. Randomized Quicksort 將 pivot 選擇從固定位置改變成隨機位置，透過亂數產生 pivot，讓一開始選取的 pivot 位置不會對其效率有太大的影響。

3. 一開始先將數列分成三個部分，分別為小於 pivot、等於 pivot 和大於 pivot 的部分。然後將小於 pivot 和大於 pivot 的部分再各自選定一個 pivot，繼續進行分區。

4. Randomized Quicksort 的時間複雜度平均為 O(nlogn)，最壞為 O(n^2)。

5. 在數列已經排好序或者都是相同元素的情況下，有可能會發生效率低落的情況，因此需要定期暫停採用 Randomized Quicksort 來處理排序。

6. Randomized Quicksort 的實現方式與普通快速排序大同小異，只是在選擇 pivot 時需要多加一些隨機的因素。

知識測驗

1. 如何避免Randomized Quicksort的最差時間複雜度O(n^2)？請說明原因及解決方法。
   答案：避免最差情況的方法之一是使用新的選擇pivot的方法，例如Median of 3或Random Median。此外，也可以使用尾遞迴或迭代版本，或者實現Randomized Quicksort的隨機樣本版本，以減少最差情況的概率。

2. 如何實現Randomized Quicksort的平均時間複雜度？請給出算法的時間複雜度和空間複雜度。
   答案：Randomized Quicksort的平均時間複雜度為O(nlogn)，空間複雜度為O(logn)。算法的關鍵在於隨機選擇pivot，並使用partition方法將數組分為兩個部分。對左側和右側的子數組遞歸地應用相同的算法，直到排序完成。

3. 如何在Randomized Quicksort中實現重複元素的處理？請說明原因及解決方法。
   答案：在Randomized Quicksort中，如果數組中存在大量重複元素，則可能導致一些情況下的最壞時間複雜度。解決此問題的一種方法是使用三向切分快速排序，將數組分為三個部分（小於、等於和大於pivot）。這樣可以避免重複元素被反覆交換，在許多情況下可以提高算法的效率。

4. 如何測試Randomized Quicksort的性能？請單獨列出利用實驗數據進行性能分析的步驟。
   答案：測試Randomized Quicksort的性能可以進行以下步驟：
   （1）選擇數據集：從不同的數據集中選擇數據，包括已排序、部分排序或完全隨機的數據。
   （2）選擇公平的比較方式：比較Randomized Quicksort和其他排序算法，如Merge Sort和Heap Sort。
   （3）記錄運行時間：使用編程語言的時間記錄功能，記錄每次運行算法花費的時間。
   （4）重複運行多次：運行算法多次以獲得平均值。
   （5）分析數據：比較不同數據集之間的性能差異，並觀察對快速排序的優化效果。

5. 如何在Randomized Quicksort中實現非遞迴版？請給出代碼實現。
   答案：
   非遞迴版Randomized Quicksort的主要思路是使用一個棧來模擬遞迴的運行過程。以下是Python代碼：

def quickSort(arr):

# Create an empty stack
stack = []

# Push initial values of l and h to stack
l = 0
h = len(arr) - 1
stack.append((l, h))

# Keep popping from stack while is not empty
while stack:

    # Pop values from stack
    (low, high) = stack.pop()

    # Set pivot element at its correct position
    p = partition(arr, low, high)

    # If there are elements on left side of pivot,
    # push the left side to stack
    if p - 1 > low:
        stack.append((low, p - 1))

    # If there are elements on right side of pivot,
    # push the right side to stack
    if p + 1 < high:
        stack.append((p + 1, high))

# Check the sorted array
return arr

def partition(arr, low, high):
i = low - 1
pivot = arr[high]
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

Test

arr = [10, 80, 30, 90, 40, 50, 70]
print(‘Original array:’, arr)

quickSort(arr)
print(‘Sorted array:’, arr)