申論題內容
假設有個矩陣A[1..n]儲存n個整數。Quick sort 是一個排序演算法。假設有個副程式
partition(A,l, r)其輸入參數A是一個矩陣，l, r,l < r < n，是兩個指標。其回傳的值m
也是一個指標。這個副程式可將矩陣中從l到r 的這一段資料A[l..r]區分成兩段：
A[l..m]和A[m +1..r]，使得在A[l..m]中的元素都小於或等於x，而在A[m +1..r]中的
元素都大於或等於x，其中x是從A[l..r]中隨機選擇的一個整數。接下來要在此兩段
資料遞迴執行partition。避免這些遞迴計算可以用一個堆疊（stack）來處理。假設
partition(A,l, r)回傳m，則執行：
if (l < m) push (l,m) into stack
if (m +1< r) push (m +1, r) into stack
一開始，堆疊中只有一組資料，(1,n)表示A[1..n]需要排序。如此反覆將堆疊最上面
的資料(l, r)移出，執行partition(A,l, r)，直到堆疊沒有資料為止。
（每小題 10 分，共20 分）
(1)證明在最糟情況下，堆疊的高度可以達到n / 2。
阿摩線上測驗
登入