110 年 - 110 交通事業港務升資考試_員級晉高員級_技術類-港務:電子計算機概論#103522-阿摩線上測驗
110 年 - 110 交通事業港務升資考試_員級晉高員級_技術類-港務:電子計算機概論#103522
二、假設 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。
請回答以下問題: