申論 5假設有個矩陣A1[..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 stackif (m+1<r) push (m +,1r) into stack一開始，堆疊中只有一組資料，,1( n )表示A1[..n]需要排序。如此反覆將堆疊最上面的資料(l ,r)移出，執行partition(A,l,r)，直到堆疊沒有資料為止。（每小題10 分，共20 分）㈠證明在最糟情況下，堆疊的高度可以達到n/2。㈡設計一個好的演算法以降低stack 的高度，並證明堆疊的高度最多只需要logn+1。