程式扎記: [ 資料結構 小學堂 ] 排序 : 直接合併排序法

標籤

2010年11月28日 星期日

[ 資料結構 小學堂 ] 排序 : 直接合併排序法


前言 :
當我們所要排序的資料量太大或檔案太大, 無法直接在記憶體內排序, 而須依賴外部儲存裝置時, 我們就會使用到外部排序法. 外部儲存裝置又可依照存取方式分為兩種, 如循序存取 (磁帶) 或隨機存取 (如磁碟). 要循序存取的檔案就像是串列一樣, 我們必須事先走訪整個串列才有辦法進行排序, 而隨機存取的檔案就像是陣列, 資料存取方便所以相對的排序也會比循序存取快一點, 一般來說外部排序法最常使用的就是合併排序法.

直接合併排序法 :
直接合併排序法 (Direct Merge Sort) 是外部儲存裝置最常用的排序方法, 它可以分成兩個步驟 :
1. 將欲排序的檔案分為幾個可以載入記憶體空間大小的檔案, 再使用內部排序法將各檔案內的資料排序.
2. 將第一步驟所建立的小檔案每兩個合併成一個檔案. 兩兩合併後, 把所有檔案合併成一個檔案後就可以完成排序.

例如 : 我們第一步把一個檔案分成6個小檔案 :


小檔案都完成排序後, 兩兩合併成一個較大的檔案, 最後再合併成一個檔案即可完成.


接著以一個實際範例說明, 假設我們要對一個檔案 test.txt 進行排序, 而 test.txt 裡包含 1500 筆資料, 但記憶體最多一次只能處理 300筆資料 :
步驟一 : 將 test.txt 分成五個檔案 t1~t5, 每個檔案300筆.
步驟二 : 以內部排序法對 t1~t5 進行排序.
步驟三 : 進行檔案 t1, t2 合併, 將記憶體分成三部分, 每部分可存放100筆資料, 先把 t1 及 t2 的前100筆資料放到記憶體裡, 排序後放到合併完成緩衝區, 等到緩衝區滿了之後便寫入磁碟 .
步驟四 : 重複步驟三直到完成為止.
合併的方法如下 :
假設我們有兩個完成排序的檔案要合併, 排序由小到大 :
a1: 1,4,6,8,9
a2: 2,3,5,7

首先在兩個檔案中分別讀出一個元素進行比較, 比較後將較小的檔案放入合併緩衝區內.
Step1 : 1與2 比較後將較小的1放進緩衝區, a1 的檔案指標往後一個元素.


Step2 : 2與4 比較後將較小的2放進緩衝區, b1 的檔案指標往後一個元素.


Step3 : 3與4 比較後將較小的3放進緩衝區, b1 的檔案指標往後一個元素.


Step4 : 4與5 比較後將較小的4放進緩衝區, a1 的檔案指標往後一個元素.

依此類推, 等到緩衝區的資料滿了就進行寫入檔案的動作; a1 或 b1 的檔案指標到了最後一筆就讀取剩下的資料完成排序.

範例代碼 :
  1. #include   
  2. #include
  3. #include   
  4. #include   
  5.   
  6. using namespace std;  
  7. void mergeSort(ofstream& fp, ifstream& fp1, ifstream& fp2) {  
  8.     char n1,n2;  
  9.     char txt1[40];  
  10.     char txt2[40];  
  11.     fp1>>n1;  
  12.     fp2>>n2;  
  13.     while(fp1.eof()==0 && fp2.eof()==0) {  
  14.         if(n1 <= n2) {  
  15.             fp.put(n1);  
  16.             fp1 >> n1; /*繼續下筆 n1資料*/  
  17.         } else {  
  18.             fp.put(n2);  
  19.             fp2 >> n2; /*繼續下筆 n2資料*/  
  20.         }  
  21.     }  
  22.     if(fp1.eof()) {  
  23.         while(!fp2.eof()) {  
  24.             fp2>>n2;  
  25.             fp.put(n2);  
  26.         }  
  27.     } else if(fp2.eof()) {  
  28.         while(!fp1.eof()) {  
  29.             fp1 >> n1;  
  30.             fp.put(n1);  
  31.         }  
  32.     }  
  33. }  
  34. void main() {  
  35.     char *data1Path = "E:/MS-VSProj/DataStructureExam/Data/data1.txt";  
  36.     char *data2Path = "E:/MS-VSProj/DataStructureExam/Data/data2.txt";  
  37.     char *dataPath = "E:/MS-VSProj/DataStructureExam/Data/data.txt";  
  38.     char txt[40];  
  39.     ofstream fp;  
  40.     ifstream fp1, fp2;  
  41.     ifstream f,f1,f2;  
  42.     fp.open(dataPath, ios::out);  
  43.     fp1.open(data1Path, ios::in);  
  44.     fp2.open(data2Path, ios::in);  
  45.     if(!fp.is_open()) {  
  46.         cout << "開啟檔案 data.txt 失敗!" << endl;  
  47.     } else if(!fp1.is_open()) {  
  48.         cout << "開啟檔案 data1.txt 失敗!" << endl;  
  49.     } else if(!fp2.is_open()) {  
  50.         cout << "開啟檔案 data2.txt 失敗!" << endl;  
  51.     } else {  
  52.         cout << "資料排序中..." << endl;  
  53.         mergeSort(fp, fp1, fp2);  
  54.         cout << "資料排序完成!!" << endl;  
  55.     }  
  56.     fp.close();  
  57.     fp1.close();  
  58.     fp2.close();  
  59.     cout << "data1.txt 資料內容為: " << endl;  
  60.     f1.open(data1Path, ios::in);  
  61.     while(!f1.eof()) {  
  62.         f1 >> txt;  
  63.         cout << txt << endl;  
  64.     }  
  65.     cout << "data2.txt 資料內容為: " << endl;  
  66.     f2.open(data2Path, ios::in);  
  67.     while(!f2.eof()){  
  68.         f2 >> txt;  
  69.         cout << txt << endl;  
  70.     }  
  71.     cout << "排序後 data.txt 資料為: " << endl;  
  72.     f.open(dataPath, ios::out);  
  73.     while(!f.eof()) {  
  74.         f >> txt;  
  75.         cout << txt << endl;  
  76.     }  
  77.     f.close();  
  78.     f1.close();  
  79.     f2.close();  
  80. }  
執行結果 :
資料排序中...
資料排序完成!!
data1.txt 資料內容為:
13578
data2.txt 資料內容為:
2469
排序後 data.txt 資料為:
123456789

補充說明 :
Algorithm Gossip: 合併排序法
合併排序法基本是將兩筆已排序的資料合併並進行排序,如果所讀入的資料尚未排序,可以先利用其它的排序方式來處理這兩筆資料,然後再將排序好的這兩筆資料合併。
有人問道,如果兩筆資料本身就無排序順序,何不將所有的資料讀入,再一次進行排序?排序的精神是儘量利用資料已排序的部份,來加快排序的效率,小筆資料的 排序較為快速,如果小筆資料排序完成之後,再合併處理時,因為兩筆資料都有排序了,所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率...
This message was edited 6 times. Last update was at 06/06/2010 13:44:27

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!