申論題

二、假設 S 為一整數型態之一維陣列，其陣列大小為 n，陣列索引從 1 開始算起，陣列元素均互異。今欲以快速排序法（quick sort）將 S 中的陣列元素由小到大排列。快速排序法其中一個很重要的動作稱為 partition（分割），其功能為：將一個稱為 pivot 的元素，擺放至正確的位置，同時將此陣列元素區分成兩半部，分別是左半部及右半部，其中左半部的元素均比 pivot 來得小，而右半部的元素均比 pivot 來得大。不失一般性，我們以陣列中的第一個元素為 pivot。以 S[]={42, 15, 73, 27, 64, 36, 54, 8}為例而言，42 即為 pivot，經過 partition 後，會有以下結果：

今將 partition 設計為一回傳整數值的函數，其形式為 int partition(int S[],int lb, int rb)，其中參數包含欲處理陣列（S）及其左邊界（lb）及右邊界（rb） ，而回傳的數值為 partition 後 pivot 所在的位置。以上例為例，S[]={42,15, 73, 27, 64, 36, 54, 8}，lb=1，rb=8，回傳的數值為 5。
請回答以下問題：