moea_joint_essay
105年
[資訊] 資訊管理、程式設計
第 六 題
處理巨量資料時，分析人員常需面對龐大資料，且資料量遠大於記憶體容量。今有一循序檔 data.txt，內含 9 筆資料如下，欲對該檔進行排序。惟受限於記憶體容量，讀入 data.txt 資料時，每次最多只能 6筆。在考量磁碟處理速度遠低於記憶體情況下，請以敘述表示法，設計一可兼顧減少磁碟存取次數及提高排序效率之排序演算法。（11 分）
data.txt
6000 800000 500 2 40 9000000 3 1.5 70000
data.txt
6000 800000 500 2 40 9000000 3 1.5 70000
📝 此題為申論題
思路引導 VIP
由於資料量大於記憶體容量，需使用外部排序(External Sorting)，最常見的是「外部合併排序法 (External Merge Sort)」。步驟分兩階段：1. 讀入記憶體大小的區塊，進行內部排序(如Quick Sort)並寫出Run檔。 2. 進行多路合併(K-way Merge)。說明本題的具體步驟：第一批6筆寫入Run1，第二批3筆寫入Run2。接著將記憶體切分為輸入緩衝與輸出緩衝，合併Run1與Run2。
🤖
AI 詳解
AI 專屬家教
為解決資料量大於記憶體的問題，並將磁碟存取 I/O 降至最低，應採用「外部合併排序演算法 (External Merge Sort)」。整體設計分為「切割與內部排序」及「外部合併」兩階段。具體步驟敘述如下： 階段一：切割與內部排序 (產生 Runs)
- 從 data.txt 循序讀入前 6 筆資料（記憶體最大容量）至記憶體中：[6000, 800000, 500, 2, 40, 9000000]。
▼ 還有更多解析內容