Merge Sort 時間複雜度分析與C++實作

Hi, I am Victor


今天跟大家介紹 合併排序法 (Merge Sort)

合併排序法的最大特色為，將一個大問題化為許多小問題，並且個個擊破~

也稱為 divide-and-conquer

步驟為:

Divide: 將大問題化作許多小問題

Conquer: 將許多小問題逐一排序

Combine: 將已經排序好的小問題合併成答案


圖解如下所示:

將原始序列分為子序列，使用 bottom-up 的方式向上個別排序與合併，

最後合併為已經排序好的序列。


虛擬碼:

Merge(A,p,q,r)
n1 = q - p + 1
n2 = r - q
create arrays L[ 1..n1 + 1 ] and R[ 1..n2 + 1 ]
for i = 1 to n1
   do L[i] = A[ p + i - 1 ]
for j = 1 to n2
   do R[j] = A[ q + j ]
L[n1+1] = Infinity
R[n2+1] = Infinity
i = 1
j = 1
for k = p to r
   do if L[i] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k]= R[j]
           j = j + 1

MERGE-SORT(A,p,r)
if p < r
   then q = floor((p + r)/ 2)
        MERGE-SORT(A,p,q)
        MERGE-SORT(A,q + 1,r)
        Merge(A,p,q,r)

演算法分析:

我們可將遞迴程式化為遞迴式，用於描述 n 個元素大小的執行時間

設 T(n)為執行時間

假如 n 足夠小則整體演算法運行時間為常數時間也就是 Theta(1)

該演算法會產生 a 個子問題，而每個子問題大小為 1 / b

假設分為許多子問題需要花 D(n)時間，而合併子問題需要花費C(n)時間，

我們原始的遞迴式會長成這樣子:

T(n) = Theta(1)
           a T(n / b) + D(n) + C(n)

讓我們再接著假設原始資料的大小都為2的次方，

所以每個子問題大小為 n / 2 ，(a=b)

Divide: 單純計算陣列的中間 index，所以花費 Theta(1) 時間

Conquer: 遞迴解 2 個子問題，一個子問題為 n / 2，所以花費 2 T(n / 2)

Combine: 我們已經知道會產生 n 子問題，所以合併花費時間為 Theta(n)


現在遞迴式變成這樣:



T(n) = Theta(1) , if n = 1
           2 T(n / 2) + Theta(n) , if n > 1

rewrite


T(n) = c , if n = 1
           2 T(n / 2) + cn , if n > 1


開始解遞迴式如下圖所示:

Total: cn lg n + cn

C++實作:

#include <iostream>
#include <climits>
using namespace std;

template <class KeyType>
class MERGESORT{
private:
    int n1,n2;
public:
   void MERGE(KeyType *A,int p,int q,int r){
        n1=q-p+1;   //n1 is elements number of left sequence
        n2=r-q;     //n2 is elements number of right sequence
        KeyType L[n1],R[n2];    //Create the left and right of sequence
        for(int i=0;i<n1;i++){
            L[i]=A[p+i];    //L [ Offset ] = A [ start + Offset ],Offset is elements number of left sequence
        }
         for(int j=0;j<n2;j++){
            R[j]=A[q+j+1];  //R [ Offset ] = A [ start + Offset ],Offset is elements number of right sequence
        }
        int i=0,j=0;
        for(int k=p;k<=r;k++){  //Conquer and combine the left and right of sequence
            if(i < n1 && j < n2){
                if(L[i]<=R[j]){
                A[k]=L[i];
                i++;
            }else{
                A[k]=R[j];
                j++;
            }
            }else if(i<n1&&j==n2){  //No need guard to check!
                A[k]=L[i];
                i++;
            }else{
                A[k]=R[j];
                j++;
            }
        }
    }

   void Merge_Sort(KeyType *A,int p,int r){ //Divide p to r
        if(p<r){
            int q=(p+r)/2;  //the q is a half of p to r size of array
            Merge_Sort(A,p,q);  //Divide p to q
            Merge_Sort(A,q+1,r);    //Divide p+1 to r
            MERGE(A,p,q,r); //conquer and combine
        }
    }
};

int main()
{
    int size=0;
    cout<<"Please key in your array size"<<endl;
    cin>>size;
    cout<<"Please key in the key of array"<<endl;
    int Array[size];
    for(int i=0;i<size;i++){
        cin>>Array[i];
    }
    MERGESORT<int> X;
    X.Merge_Sort(Array,0,size-1);
    for(int i=0;i<size;i++){
        cout<<Array[i]<<"\t";
    }
    return 0;
}

Reference book : INTRODUCTION TO ALGORITHMS (second edition)
Authors:
                  THOMAS H. CORMEN
                  CHARLES E. LEISERSON
                  RONALD L.  RIVEST
                  CLIFFORD STEIN

The C ++ code is write by myself  ; )

Thanks

By   Victor