地特四等申論題
114年
[統計] 資料處理概要
第 一 題
📖 題組：
二、QuickSort 和 MergeSort 是常見的排序演算法，各自有優點與缺點。
二、QuickSort 和 MergeSort 是常見的排序演算法，各自有優點與缺點。
📝 此題為申論題，共 3 小題
小題 (一)
假設你負責設計一個「線上圖書目錄系統」，需要對 50 萬筆已經按照「出版年份」由大到小排序的書籍資料，重新依照「作者名稱」排序，讓使用者能快速找到作者撰寫的書，但同時需要保持同一作者撰寫的書籍能依據原本出版年份順序排列。根據 QuickSort 和 MergeSort 兩種演算法的特性，你會選擇那一種演算法？為什麼？（10 分）
思路引導 VIP
這題的核心考點是排序演算法的「穩定性 (Stability)」。題目要求在依「作者名稱」排序後，同作者的書要「保持原本的出版年份順序」。這正是穩定排序的定義（鍵值相同時，維持原本的相對順序）。接著對比 QuickSort（不穩定）與 MergeSort（穩定）的特性，答案呼之欲出。
小題 (二)
有一個數列[39, 18, 61, 46, 11, 2, 24, 33]，利用 QuickSort（以第一個元素為基準）進行由小到大的排序，請寫出並說明每一次循環的結果。（10 分）
思路引導 VIP
本題要求模擬 QuickSort 第一個循環（Partition）的過程。需明確指出 Pivot（基準點）為第一個元素(39)。使用標準的從兩端逼近的指標法（Left 和 Right 指標）：Left 往右找大於 Pivot 的值，Right 往左找小於 Pivot 的值，找到則交換。直到兩指標交會，最後將 Pivot 與交會處（或 Right 指標停留處）交換，完成第一回合分割，左邊皆小於 39，右邊皆大於 39。
小題 (三)
與上面問題同一個數列，利用 MergeSort 進行由小到大的排序，請寫出並說明每一次循環的結果。（10 分）
思路引導 VIP
本題測驗 MergeSort 的 Bottom-Up（或 Top-Down 分解後再合併）合併過程。需將原始數列先視為 8 個獨立長度為 1 的子數列，然後進行兩兩合併：先合併成長度為 2，再合併成長度為 4，最後合併成長度為 8 的完整排序數列。清楚標示出每一個 Pass（回合）合併後的狀態。