第 四 題

本題的核心在於將工廠自動化排序的情境，映射到資料結構中的「氣泡排序（Bubble Sort）」演算法。考生需思考「相鄰交換」的特性，並評估在最差情況下（數列完全反序），需要多少回合（Passes）或多少次比較交換（Comparisons）才能保證排序完成。

看到此題應立刻聯想到「氣泡排序法（Bubble Sort）」的應用，每個機器人代表一次從頭到尾的陣列掃描（Pass）。解題時可透過逐步追蹤（Trace）每次掃描後的陣列變化，或利用氣泡排序中元素逆向移動的最大距離（烏龜現象）來精確計算所需的最少機器人數量。

考生看到這題應立刻聯想到「氣泡排序（Bubble Sort）」的演算法特性。機器人比較相鄰兩球並交換的動作，等同於氣泡排序中的一次掃描（Pass）。在降序排序中，每次掃描能讓較大的數字最多「向左前進 1 格」，因此最少需要的機器人數量，就等於所有數字中「初始位置與其目標位置向左差距的最大值」。

本題核心在於辨識「機器人排序相鄰兩球」的行為等同於氣泡排序（Bubble Sort）的一次掃描（Pass）。要讓序列經過 4 次掃描仍未排好，需利用氣泡排序中「大元素每次只能往前移動一格」的特性（即烏龜元素），設計出由小到大遞增的極端逆向序列。

將機器人對連續經過的球進行相鄰交換的動作，映射為演算法中的「氣泡排序法（Bubble Sort）」的單一回合（Pass）。接著分析 n 個元素在氣泡排序中最差情況所需的最大回合數，即可判斷增加機器人是否能提升效率。