[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，我希望從現在開始實現這個願望，目前註解法的格式還在制定中。

[演算法] Loop Invariants

        Loop Invariant 是證明某個不變的條件(稱為Invariant Condition)，這個條件在程式進入迴圈前跟進入迴圈後，此條件仍不變。

通常以while迴圈為例子。
假如有一個while迴圈如下：

while( A )
{
        //Body..
}

        那麼假設一個 Invariant 條件叫做 X ，這個X條件在while檢查A條件時都維持原狀，一進入Body 時可能改變X條件，但一執行完 Body 後 X 又恢復原貌，這種條件就是一個典型的 Invariant Condition。

• 證明Loop Invariant需要三個步驟：
  1.   Initialization：描述 Invariant Condition 在迴圈執行第一個 iteration前，就成立。
  2.   Maintenance：描述 Invariant Condition 在迴圈的任一iteration執行前跟執行後都維持成立。
  3.   Termination：迴圈執行結束後，Invariant Condition 能夠展示整體演算法的正確性。

[演算法] 以UVA第10107程式題目複習Insertion Sort

首先複習一下 Insertion Sort。

Insertion Sort       
Insertion Sort的精神是當在排序一個數字陣列時，每當處理一個數字，就代表在這個數字之前的數都已經排序好了。因此只需要將這個數字跟前面排好的數字序列比較，並將目前處理的這個數字insert到之前排序好的序列中，就像一般在玩撲克牌時通常會使用的排序法。

        以下是我練習將InsertionSort的Code用C++寫出：
void InsertionSort()
{
     int key = 0;
     for(int j=1;j<size;j++)
     {
             key = data[j];
             int i = j-1;
             while(i>=0 && data[i]>key)
             {
                        data[i+1] = data[i];
                        i--;
             }
             data[i+1] = key;
     }
}
UVA #10107(What is the median)
這個題目給的Sample Input跟Sample Output如下：

Sample Input

1
3
4
60
70
50
2

Sample Output

1
2
3
3
4
27
4

        本題的目標為每從Sample Input讀進一個數字到序列中，就找出當下的中位數(median)，如果總共有奇數個數字，則將取排序好的數列的中間兩個數字相加除以2，除以2後只取整數部分。

思考方式：
        使用Insertion Sort的原因，是因為這題是每讀到一個數字就做排序，所以當讀進一個新數字時，之前的讀過的數字都已經排序好了，所以只須將新讀入的數字Insert到前面排序好的序列的適當位置，這很符合Insertion Sort的基本概念。

以下是我解決此題目的Code：(implement using C++)

//main.cpp
//The excution result is correct, and is accepted by UVA Online Judge.
//This is the code for UVA Online Judge #10107
//This code was created by Uncle on 2012/03/03
#include<iostream>
#include<sstream>
#include<fstream>
using namespace std;
int *data = NULL;
int size = 0;

int *Expand(int *arrReceive,int &s,int key)
{
    int *newArr = new int [s+1];
    for(int i=0;i<s;i++)
    {
        newArr[i] = arrReceive[i];
    }
    newArr[s] = key;
    delete []arrReceive;
    s++;
    return newArr;
}
void InsertionSort()
{
     int key = 0;
     for(int j=1;j<size;j++)
     {
             key = data[j];
             int i = j-1;
             while(i>=0 && data[i]>key)
             {
                        data[i+1] = data[i];
                        i--;
             }
             data[i+1] = key;
     }
}
int main()
{
    int key;
    ifstream inputFile;
    //inputFile.open("input.txt",ifstream::in);
    while(cin >> key)
    {
                    data = Expand(data,size,key);
                    InsertionSort();
                    if(size%2)  //total size is odd
                    {
                              cout << data[size/2] << endl;
                    }
                    else
                    {
                        int tmp = data[(size/2)-1] + data[size/2];
                        tmp = tmp/2;
                        cout << tmp << endl;
                    }
    }
    //getchar();
    return 0;
}

---