AY 22-23 Final Exam - Question B3（Sorting & Big-O）

這題佔了整整 20 分，分為 (a) 排序演算法追蹤 以及 (b) Big-O 時間複雜度計算 兩個部分。以下為詳細的批改與費曼解析！

👨‍🏫 教授的破題口訣 (Professor's Hints)：

Insertion Sort (插入排序)：就像整理手上的撲克牌，每次把下一個數字插進左邊正確的位置。
Bubble Sort (氣泡排序)：由大排到小卻要求排成遞增，每一個數字都要交換最多次，這是最壞情況 (Worst Case)！
Merge Sort (合併排序)：Divide and Conquer (分割與征服)。先切到最小，再兩兩、四四合併排好順序！
Quick Sort (快速排序)：巡邏指標 i 走到底，看到「比 pivot 小」的數字，就把它跟 storeIndex 交換，然後 storeIndex++。
Big-O 複雜度：「忽略常數 (Drop the constants)，只看最關鍵的成長趨勢！」看到迴圈用加減的通常是 O(n)，看到乘除倍數逼近的通常是 O(log n)。

Part (a): Sorting Algorithms (15 marks)

目標：將數列 33, 30, 57, 41, 74, 18, 52, 60 以遞增順序排序。

(i) 插入排序 (Insertion Sort) 每一次 Pass 的結果

✅ 你的答案：完美！(3/3 marks)

初始: 33, 30, 57, 41, 74, 18, 52, 60
Pass 1: [30 33] 57 41 74 18 52 60
Pass 2: [30 33 57] 41 74 18 52 60
Pass 3: [30 33 41 57] 74 18 52 60
Pass 4: [30 33 41 57 74] 18 52 60
Pass 5: [18 30 33 41 57 74] 52 60
Pass 6: [18 30 33 41 52 57 74] 60
Pass 7: [18 30 33 41 52 57 60 74]

教授點評：你完美地展現了「撲克牌插入」的邏輯，每一次 Pass 都精準地把下一個數字放進左邊已排好序的陣列中！

(ii) 氣泡排序最壞情況複雜度 (Bubble Sort Worst-Case)

✅ 你的答案：n^2 (1/1 mark)

教授點評：觀念完全正確！但在正式考卷上，請務必記得加上 Big-O 的括號，寫成 O(n²) 才能穩穩拿分喔！

(iii) 合併排序 (Merge Sort) 追蹤

✅ 你的答案：精準！(4/4 marks)

[33 30 57 41] [74 18 52 60]
[33 30][57 41][74 18][52 60]
[30 33][41 57][18 74][52 60]
[30 33 41 57][18 52 60 74]
[18 30 33 41 52 57 60 74]

教授點評：你把 Divide and Conquer 的精神發揮得淋漓盡致。從 8個切成 4-4、2-2，再完美地合併，這 4 分拿得實至名歸。

(iv) 快速排序追蹤 (Quick Sort Tracing)

⚠️ 批改：掉進指標陷阱了 (0/5 marks)

你的答案從 Step 3 開始亂掉了，把 storeIndex 的用途搞混了。storeIndex 就像是一個「小於 33 的專屬座位區邊界」。我們來一步步走：

初始: 33, 30, 57, 41, 74, 18, 52, 60 (Pivot=33, storeIndex=1)

Step 1 (val=30): 30 < 33 ➔ 丟進 storeIndex(1)，自己跟自己交換沒變化。storeIndex 變成 2。
[ 33, 30, 57, 41, 74, 18, 52, 60 ] | storeIndex = 2

Step 2 (val=57): 57 > 33 ➔ 不理它，storeIndex 停在 2。
Step 3 (val=41): 41 > 33 ➔ 不理它，storeIndex 停在 2。
Step 4 (val=74): 74 > 33 ➔ 不理它，storeIndex 停在 2。

Step 5 (val=18): 18 < 33 ➔ 抓到了！跟 storeIndex(2) 的位子(57)交換！
[ 33, 30, 18, 41, 74, 57, 52, 60 ] | storeIndex 變成 3

Step 6 (val=52): 52 > 33 ➔ 不理它。
Step 7 (val=60): 60 > 33 ➔ 不理它。

Step 8 (Swap Pivot): 把 Pivot(33) 跟 storeIndex - 1 (Index 2 的 18) 交換！
✅ 最終正確答案：[ 18, 30, 33, 41, 74, 57, 52, 60 ]

(v) Quick Sort Pivot Selection (基準選擇)

⚠️ 你的答案：中間的數字愈小 (0/2 marks)

👨‍🏫 教授的理論解析：這題考的是「資料的初始狀態」對效能的影響。如果資料「已經排好序了」，你總是選「第一個數字」當 pivot，切出來的兩半會是 0 個與 n-1 個，會讓 Quick Sort 退化成 O(n²) 的最壞情況！

選「中間的數字」當 pivot，能把它完美切成一半一半，效能維持在最佳的 O(n log n)。

Part (b): Big-O 時間複雜度計算 (5 marks)

考驗判斷程式碼執行效率的眼力！抓到迴圈變數 (loop variable) 的變化規律就能秒殺。

(i) 迴圈：線性遞減

int sum = 0;
for (int i=n+1000; i>=1; i-=10)
    sum += i;

⚠️ 你的答案：n/2 (0/1 mark)

✅ 正確答案：O(n)

👨‍🏫 教授點評：你觀察到它執行了約 (n+1000)/10 次。但在 Big-O 的世界裡，黃金法則必背：「忽略所有常數 (Drop the constants)」！只要迴圈是以固定的步距做加減，它就是線性的 O(n)。

(ii) 迴圈：指數成長

int sum = 0;
for (int i=1; i<=n; i*=3)
    sum += i;

⚠️ 你的答案：nlogn (0/2 marks)

✅ 正確答案：O(log n)

👨‍🏫 教授點評：觀察 i*=3！它的成長軌跡是 1, 3, 9, 27, 81... 呈指數級暴增！只要是用「乘法 (*) 或除法 (/) 以倍數朝邊界逼近」，時間複雜度就是對數級別 O(log n)。

(iii) 巢狀迴圈：外層線性 + 內層對數

int sum = 0;
for (int i=1; i<=n/2; i++)
    for (int j=n; j>1; j/=3)
        sum += (i*j);

⚠️ 你的答案：n^2logn (0/2 marks)

✅ 正確答案：O(n log n)

👨‍🏫 教授點評：巢狀迴圈要把外層與內層「相乘」。外層是 i++ 到 n/2，複雜度為 O(n)；內層是 j/=3 到 1，複雜度為 O(log n)。兩者相乘即為 O(n log n)。你多給了一個平方，要小心不要混淆了！