程式扎記: [ 資料結構 小學堂 ] 排序 : 改良氣泡排序法

標籤

2010年12月6日 星期一

[ 資料結構 小學堂 ] 排序 : 改良氣泡排序法

前言 : 
由傳統泡沫排序法可以看出有一個缺點是不管資料是否以排序完成都固定會執行 n(n-1)/2 次, 而我們可以藉由在程式中加入一判斷式來加以判斷何時可以提前中斷程式, 又可以得到正確的資料, 來增加程式的執行效能. 

範例代碼 : 

  1. #include   
  2.   
  3. using namespace std;  
  4.   
  5. struct BenchMark {  
  6.     int swapTime;  
  7.     int verifyTime;  
  8. };  
  9. BenchMark advanceBubbleSort(int data[], int n) {  
  10.     int cnt = 0, vt=0, flag=0;  // flag 是用來判斷是否已完成排序並跳出的比較的迴圈  
  11.     BenchMark bm;  
  12.     for(int i=n-1; i>0; i--) {  
  13.         flag = 0;  
  14.         for(int j=0; j
  15.             vt++;  
  16.             if(data[j+1] < data[j]) {  
  17.                 int tmp = data[j+1];  
  18.                 data[j+1] = data[j];  
  19.                 data[j] = tmp;  
  20.                 cnt++;  
  21.                 flag++;  
  22.             }  
  23.         }  
  24.         if(flag==0) { // 完成排序, 故不需要 swap  
  25.             break;  
  26.         }  
  27.     }  
  28.     bm.swapTime = cnt;  
  29.     bm.verifyTime = vt;  
  30.     return bm;  
  31. }  
  32. void main(bool b) {  
  33.     if(b) {  
  34.         int data[6] = {2,5,9,7,6,8};  
  35.         cout<< "原始資料: " << endl;  
  36.         for(int i=0; i<6; i++) {  
  37.             printf("%2d ",data[i]);  
  38.         }  
  39.         printf("\n");  
  40.         BenchMark bm = advanceBubbleSort(data, 6);  
  41.         cout << "改良泡沫排序: " << endl;  
  42.         for(int i=0; i<6; i++) {  
  43.             printf("%2d ",data[i]);  
  44.         }  
  45.         printf("\n");  
  46.         printf("Swap time: %d\n", bm.swapTime);  
  47.         printf("Verify time: %d\n", bm.verifyTime);  
  48.     }  
  49. }  
執行效果 : 

原始資料:
2 5 9 7 6 8
改良泡沫排序:
2 5 6 7 8 9
Swap time: 4
Verify time: 12 <執行次數小於 n(n-1)/2, n=6 => 15>

沒有留言:

張貼留言

網誌存檔

關於我自己

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