Pages

2012年3月4日 星期日

[Bug研究] Merge Sort的Bug

        我寫過很多次Merge Sort,有時寫完會有一些Bug。
以下是我這次用C++寫的一個有Bug的Merge Sort函式,這個錯誤一開始我並沒有很快找出:


   1: void MergeSort(int *A, int p, int r)
   2: {
   3:      int q = 0;
   4:      if(p<r)
   5:      {
   6:             q = ((p+r)/2);
   7:             MergeSort(A,p,q);
   8:             MergeSort(A,q+1,r);
   9:             Merge(A,p,q,r);
  10:      }
  11: }
  12: void Merge(int *A, int p, int q, int r)
  13: {
  14:      int n1 = q-p+1;   //number of elements of left array. Include q.
  15:      int n2 = r-q;     //number of elements of right array.
  16:      int L[n1+1];
  17:      int R[n2+1];
  18:      
  19:      for(int i=0;i<n1;i++)
  20:      {
  21:              L[i] = A[p+i];
  22:      }
  23:      for(int j=0;j<n2;j++)
  24:      {
  25:              R[j] = A[q+j];
  26:      }
  27:      L[n1] = infinite;
  28:      R[n2] = infinite;
  29:      int i = 0;  int j = 0;
  30:      
  31:      for(int k=p;k<=r;k++)
  32:      {
  33:              if(L[i]<=R[j])
  34:              {
  35:                  A[k] = L[i];
  36:                  i++;
  37:              }
  38:              else
  39:              {
  40:                  A[k] = R[j];
  41:                  j++;
  42:              }
  43:      }
  44: }




這個程式執行結果會是錯的,原因是第25行:
  25:              R[j] = A[q+j];

在複製陣列內容到R array時,應該要寫:
  25:              R[j] = A[q+j+1];
因為L陣列裡面已經包含index為 q 的element了。只要更改這一行,就是一個完整的Merge Sort的code了。

我將這種bug歸類為"陣列index的錯誤問題"。這種bug通常簡單,但簡單的錯誤難免發生。為了避免類似的錯誤,我之後將會使用特定格式的註解(先將此註解法則命名為Uncle註解法好了...),來表示出陣列操作時的操作範圍,例如
,以此Merge Sort為例:
   
      R[j] = A[q+j+1];       // A[] : q+1<->q+n2 // j : 0<->n2-1 // total # : n2

上面這一行的註解中 A[] : q+1<->q+n2代表陣列A的索引值在for迴圈中從q+1一直trace到q+n2範圍,每一部分的註解描述用雙斜線 "//" 分開,j : 0<->n2-1代表j從0一直到n2-1,最後 total # : n2代表整體迴圈操作次數有n2+1次操作。

一直以來我都想定義一個共同的註解規範,能夠註解的格式統一,方便debug,我希望從現在開始實現這個願望,目前註解法的格式還在制定中。

沒有留言:

張貼留言