iT邦幫忙

2021 iThome 鐵人賽

DAY 6
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 6

Day-6 Divide-and-Conquer-1 : merge sort

設計演算法

我們可以選擇的演算法設計技術有很多種。插入排序使用了遞增逼近(incremental approach)的方法 : 在排序子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5B1%2C...%2C%20j%20-%201%5D之後,將單個元素https://chart.googleapis.com/chart?cht=tx&chl=A%5Bj%5D插入子陣列的適當位置,產生出完成排列的子陣列。

分治法(Divide-and-Conquer)

有許多演算法使用了遞迴的結構進行設計 : 為了解決一個問題,將問題拆分後經過多次遞迴解決問題的子問題,最終合併結果並解決問題。這種演算法就是分治法的想法。分治法在每一層的遞迴會有三個步驟:

  • 分解(Divide) : 將原問題分解成許多個子問題,每一個子問題都是原問題規模較小的實例。
  • 解決(Conquer) : 遞迴的方式去求解各子問題,當子問題的規模夠小時,則直接求解。
  • 合併(Combine) : 將子問題的解合併成原問題的解。

合併排序法(merge sort)

合併排序法(merge sort)就是一種由分治法實現的演算法,直觀上也是符合分治法的三個步驟

  • 分解(Divide) : 分解待排序長度為https://chart.googleapis.com/chart?cht=tx&chl=n的陣列,變成長度為https://chart.googleapis.com/chart?cht=tx&chl=n%2F2長度的兩個子陣列。
  • 解決(Conquer) : 使用合併排序法遞迴的排序兩個子陣列。
  • 合併(Combine) : 合併兩個已經排序的子陣列產生出已經完成排序的原陣列。

當子陣列的長度為1時,表示子陣列已經完成排序,並開始合併去完成排序每一個子陣列。

合併排序法關鍵的操作步驟為'合併',將兩個以排序的子陣列合併。我們通過MERGE(A, p, q, r)來完成合併,A為陣列,https://chart.googleapis.com/chart?cht=tx&chl=p%2C%20q%20%2C%20r為陣列的下標,滿足https://chart.googleapis.com/chart?cht=tx&chl=p%3C%3Dq%3C%3Dr。在合併的過程中,我們假設子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp...q%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=A%5Bq%20%2B%201...r%5D都已經完成排序。將這兩個子陣列合併形成新的一個已經完成排序,規模更大的子陣列,並替換掉目前的子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp...r%5D

合併的過程大約需要Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n)的時間,其中https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%20r%20-%20p%20%2B%201是整個待排序陣列的元素個數。整個合併大概會執行以下操作。想像桌上有兩堆牌面朝上的撲克牌,每一堆都已經完成排序,最小的牌在每一堆的最上面。我們希望把這兩堆牌合併成單一已經排好序的撲克牌堆,並且完成之後牌面向下放在桌上。

來源

我們的操作為在牌面朝上的兩堆牌上選取最上面那一張,在這兩張牌中選出最小的那一張牌,把這張牌從剛剛的撲克牌堆移除,將這張牌牌面向下放置在桌上另外的位置,成為新的撲克牌堆,我們稱這一個堆為輸出堆。不斷重複這個步驟,直到有一堆撲克牌堆沒有撲克牌為止,這時候,我們只要拿起剩下一開始的撲克牌堆並將牌面向下放置到輸出堆。因為每一次我們只比較兩個撲克牌堆最上面的那張牌,計算每一個步驟都需要常數時間https://chart.googleapis.com/chart?cht=tx&chl=c_i。最多執行n個步驟,因此合併需要Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n)的時間。

下面的虛擬碼呈現了合併的作法,但我們加了一張額外的牌,這張牌的功用是避免每一個比較步驟都要檢查撲克牌堆是否為空的,這張牌我們稱為哨兵牌(Sentinel value),或是信號牌(signal value),它包含一個特殊的數值,可以幫助我們簡化程式碼,我們設這個值為∞,這張牌必定會在每一個撲克牌堆的最下方(因為沒有數值比他大),當我們看到某一堆露出哨兵牌,表示這個撲克牌堆為空,如果發生兩個堆都露出哨兵牌,則我們可以知道所有非哨兵牌都已經放入輸出堆。

MERGE(A, p, q, r)
A表示輸入的牌組,p表示L的起始index(A的起始index),q為R的起始index(A的中間index),r表示A的尾index。

n1 = q - p + 1
n2 = r - q
let L[1...n1 + 1] and R[1...n2 + 1] be new arrays
for i = 1 to n1
    L[i] = A[p + i - 1]
for j = 1 to n2
    R[j] = A[q + j]
L[n1 + 1] = ∞
R[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
    if L[i] <= R[j]
        A[k] = L[i]
        i = i + 1
    else A[k] = R[j]
        j = j + 1


第10行以前表示將A陣列猜分成兩個部分,左子陣列和右子陣列,第12行迴圈,k從給定的A陣列起始index p開始,一路走訪到結束index r,i和j表示左子陣列的index和右子陣列的index,如圖(a)表示。

進入迴圈迭代,比較https://chart.googleapis.com/chart?cht=tx&chl=L%5B0%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=R%5B0%5D,發現https://chart.googleapis.com/chart?cht=tx&chl=L%5B0%5D%20%3C%20R%5B0%5D,因此將R[0]放入A陣列中,並將R的index j往後走一格,表示1已經放入A陣列中,A陣列的index k也往後走一格,如圖(b)所示。

不斷進入迭代,進行比較後放入A陣列中,如果其中一個子陣列碰到無限大,則表示該陣列所有元素已經放入A陣列中。

整個MERGE具體的執行過程如下:

  • 第1行表示子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp..q%5D的長度https://chart.googleapis.com/chart?cht=tx&chl=n_1
  • 第2行表示子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bq%20%2B%201..r%5D的長度https://chart.googleapis.com/chart?cht=tx&chl=n_2
  • 第3行宣告長度分別為https://chart.googleapis.com/chart?cht=tx&chl=n_1%20%2B%201https://chart.googleapis.com/chart?cht=tx&chl=n_2%20%2B%201的陣列L和R,每個陣列保留多1的長度是為了放入哨兵牌。
  • 第4行到第5行的for迴圈將子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp..q%5D複製到https://chart.googleapis.com/chart?cht=tx&chl=L%5B1..n_1%5D
  • 第6行到第7行的for迴圈將子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bq%20%2B%201..r%5D複製到https://chart.googleapis.com/chart?cht=tx&chl=R%5B1..n_2%5D
  • 第8行到第9行將哨兵放入陣列L和R的末端
  • 第10行到第17行經過循環不變式,執行https://chart.googleapis.com/chart?cht=tx&chl=r%20-%20p%20%2B%201個基本步驟:
    • 在開始第12行到第17行for迴圈的每一次迭代,子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp..k%20-%201%5D按照從小到大排序,包含https://chart.googleapis.com/chart?cht=tx&chl=L%5B1..n_1%20%2B%201%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=R%5B1..n_2%20%2B%201%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=k%20-%20p個最小元素,得出https://chart.googleapis.com/chart?cht=tx&chl=L%5Bi%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=R%5Bj%5D是各自在陣列中還沒被複製回A陣列的最小元素。

我們需要證明第12行到第17行for迴圈的第一次迭代之前循環不變式成立,每一次迭代之前也成立,最後一次迭代結束後也成立。這個循環不變式提供某些性質幫助我們證明正確性。

  • 初始化 : 在第一次迭代之前,for的初始條件https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%20p,所以https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp..k%20-%201%5D為空。這個空的子陣列裡面包含L和R的https://chart.googleapis.com/chart?cht=tx&chl=k%20-%20p%20%3D%200個最小元素,又因為https://chart.googleapis.com/chart?cht=tx&chl=i%20%3D%20j%20%3D%201,所以https://chart.googleapis.com/chart?cht=tx&chl=L%5Bi%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=R%5Bj%5D都是各自所在的陣列中未被複製到A陣列的最小元素。

  • 保持 : 我們假設https://chart.googleapis.com/chart?cht=tx&chl=L%5Bi%5D%20%3C%3D%20R%5Bj%5D。這時候,https://chart.googleapis.com/chart?cht=tx&chl=L%5Bi%5D是沒有放回A陣列的最小元素,子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp..k%5D包含https://chart.googleapis.com/chart?cht=tx&chl=k%20-%20p%20%2B%201個最小元素。在for中增加k值和i值,為了下次迭代重新建立了該循環不變式。若https://chart.googleapis.com/chart?cht=tx&chl=L%5Bi%5D%20%3E%20R%5Bj%5D,則第16到17行執行適當的操作來維持循環不變式。

  • 終止 : 終止時https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%20r%20%2B%201。根據循環不變式,子陣列https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp..k%20-%201%5D就是https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp..r%5D由小到大排序,且包含https://chart.googleapis.com/chart?cht=tx&chl=L%5B1..n_1%20%2B%201%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=R%5B1..n_2%20%2B%201%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=k%20-%20p%20%3D%20r%20-%20p%20%2B%201個最小元素。陣列L和R一起包含https://chart.googleapis.com/chart?cht=tx&chl=n_1%20%2B%20n_2%20%2B%202%20%3D%20r%20-%20p%20%2B%203個元素。除兩個哨兵元素外,其他元素都已經放入A陣列中。

我們已知https://chart.googleapis.com/chart?cht=tx&chl=n%20%3D%20r%20-%20p%20%2B%201,第1到3行和第8到11行每一行都需要常數時間https://chart.googleapis.com/chart?cht=tx&chl=c_i,第4到7行的for迴圈需要Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n_1%20%2B%20n_2)%20%3D%20Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n)的時間,第12行到17行的for迴圈有n次迭代,每一次迭代也需要常數時間。

MERGE-SORT的主要想法,就是將兩個子陣列MERGE-SORT之後,在MERGE起來,會將https://chart.googleapis.com/chart?cht=tx&chl=A%5Bp..r%5D猜分成兩個子陣列https://chart.googleapis.com/chart?cht=tx&chl=L%5Bp..q%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=R%5Bq%20%2B%201..r%5D,前者和後者均有https://chart.googleapis.com/chart?cht=tx&chl=n%2F2個元素。

MERGE-SORT(A, p, r)

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

不斷將陣列拆分成兩個子陣列,之後再作合併

合併排序在https://chart.googleapis.com/chart?cht=tx&chl=A%20%3D%20%7B%205%2C2%2C4%2C7%2C1%2C3%2C2%2C6%20%7D上進行操作,不斷地向上推進,合併以排序的子陣列。

以下為C++實作

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;
void merge(vector<int> &A, int, int, int);
void merge_sort(vector<int> &A, int, int);
int main(void)
{
    ios::sync_with_stdio(0), cin.tie(0);
    int A[10] = {2, 4, 1, 6, 7, 3, 9, 0, 3, 1};
    vector<int> array(A, A + sizeof(A) / sizeof(int));
    cout << "Original" << '\n';
    for(auto i : array)
    {
        cout << i << ' ';
    }
    cout << "After merge_sort << '\n'";
    merge_sort(array, 0, 9);//放入起始index和結束index
    for(auto i : array)
    {
        cout << i << ' ';
    }
}

void merge(vector<int> &array, int front, int mid, int end)
{
    vector<int> Left_sub(array.begin() + front, array.begin() + mid + 1);
    vector<int> Right_sub(array.begin() + mid + 1, array.begin() + end + 1);

    Left_sub.insert(Left_sub.end(), INT_MAX);
    Right_sub.insert(Right_sub.end(), INT_MAX);

    int Left_index = 0;
    int Right_index = 0;

    for (int i = front; i <= end; i++)
    {
        if(Left_sub[Left_index] <= Right_sub[Right_index])
        {
            array[i] = Left_sub[Left_index];
            Left_index++;
        }
        else
        {
            array[i] = Right_sub[Right_index];
            Right_index++;
        }
    }
}

void merge_sort(vector<int> &array, int front ,int end)
{
    if (front < end)
    {
        int mid = (front + end) / 2;
        merge_sort(array, front, mid);
        merge_sort(array, mid + 1, end);
        merge(array, front, mid, end);
    }
}

分析分治演算法

當一個演算法包含呼叫自身遞迴時,我們會使用遞迴關係式去描述他所花費的時間。

分治法運行時間的遞迴關係式來自分解,合併,解決這三個步驟。假設https://chart.googleapis.com/chart?cht=tx&chl=T(n)為規模為n的一個問題所需要的運行時間。如果問題的規模足夠小時,如對某個常數https://chart.googleapis.com/chart?cht=tx&chl=chttps://chart.googleapis.com/chart?cht=tx&chl=n%20%3C%3D%20c,則直接求解即需要常數時間,我們用 Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1)表示。假設我們將原問題分解成https://chart.googleapis.com/chart?cht=tx&chl=a個子問題,每一個子問題的規模都是原問題的https://chart.googleapis.com/chart?cht=tx&chl=1%2Fb(對於合併排序來說,a和b皆為2)。為了求解一個規模為https://chart.googleapis.com/chart?cht=tx&chl=n%2Fb的子問題,需要https://chart.googleapis.com/chart?cht=tx&chl=T(n%2Fb)的時間,所以需要https://chart.googleapis.com/chart?cht=tx&chl=aT(n%2Fb)的時間來解決https://chart.googleapis.com/chart?cht=tx&chl=a個子問題。如果將原問題拆分成多個子問題需要https://chart.googleapis.com/chart?cht=tx&chl=D(n)的時間,合併多個子問題的解成為原問題的解需要https://chart.googleapis.com/chart?cht=tx&chl=C(n)的時間,那麼得到以下遞迴關係式 :

合併排序分析

雖然合併排序在輸入陣列不是偶數也同樣可以作用,但是,假定原問題的規模是https://chart.googleapis.com/chart?cht=tx&chl=2%5En,那麼我們可以對遞迴式的分析進行簡化。每一步的分解都會剛好產生出https://chart.googleapis.com/chart?cht=tx&chl=n%20%2F%202的兩個子陣列。其實我們這樣的假設不會影響到遞迴式的量級,後續會詳細說明。

下面我們分析建立合併排序n個數的最壞情況的運行時間https://chart.googleapis.com/chart?cht=tx&chl=T(n)的遞迴式。合併排序一個元素需要常數時間https://chart.googleapis.com/chart?cht=tx&chl=c_i。當有https://chart.googleapis.com/chart?cht=tx&chl=n%20%3E%201個元素時,我們分解運行時間如下:

  • 分解 : 分解步驟僅需要知道子陣列的中間位置,需要常數時間,因此https://chart.googleapis.com/chart?cht=tx&chl=D(n)%20%3D%20Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1)
  • 解決 : 遞迴的求解兩個規模均為https://chart.googleapis.com/chart?cht=tx&chl=n%2F2的子問題,需要https://chart.googleapis.com/chart?cht=tx&chl=2T(n%20%2F%202)的時間
  • 合併 : 具有n個元素的子陣列MERGE過程需要Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n)的時間,所以https://chart.googleapis.com/chart?cht=tx&chl=C(n)%3DΘhttps://chart.googleapis.com/chart?cht=tx&chl=(n)

當為了分析合併排序的運行時間而將https://chart.googleapis.com/chart?cht=tx&chl=D(n)https://chart.googleapis.com/chart?cht=tx&chl=C(n)函數相加時,我們是把一個函數Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n)和另一個Θhttps://chart.googleapis.com/chart?cht=tx&chl=(1)函數相加。得出來的結果是一個n的線性函數,也就是Θhttps://chart.googleapis.com/chart?cht=tx&chl=(n),再將這個函數和解決的部分相加,得到以下最差運行時間https://chart.googleapis.com/chart?cht=tx&chl=T(n)的遞迴關係式

常數https://chart.googleapis.com/chart?cht=tx&chl=c代表合併排序規模為1的問題所需要的時間。

下圖展示了如何求解遞迴式,假設https://chart.googleapis.com/chart?cht=tx&chl=n剛好為https://chart.googleapis.com/chart?cht=tx&chl=2%5En
(a)部分展示https://chart.googleapis.com/chart?cht=tx&chl=T(n)
(b)部分展示一棵被擴展成描述遞迴式的樹。https://chart.googleapis.com/chart?cht=tx&chl=c_n表示樹根(遞迴的最頂層),根的兩個子樹為較小的遞迴式https://chart.googleapis.com/chart?cht=tx&chl=T(n%2F2)
(c)部分展示https://chart.googleapis.com/chart?cht=tx&chl=T(n%2F2)再被拆解的過程。在第二層的遞迴中,兩個子節點中所需的運行時間為https://chart.googleapis.com/chart?cht=tx&chl=cn%2F2,不斷分截直到規模下降到1
(d)部分展示了整個遞迴樹,並推出結果

高度為https://chart.googleapis.com/chart?cht=tx&chl=log_2n,總共有https://chart.googleapis.com/chart?cht=tx&chl=log_2n%2B1層,整體時間為https://chart.googleapis.com/chart?cht=tx&chl=cnlgn%2Bcn(https://chart.googleapis.com/chart?cht=tx&chl=lg表示https://chart.googleapis.com/chart?cht=tx&chl=log_2),表示為Θhttps://chart.googleapis.com/chart?cht=tx&chl=(nlgn)

我們將每一層所需要的運行時間相加,頂層為https://chart.googleapis.com/chart?cht=tx&chl=c_n,下一層為https://chart.googleapis.com/chart?cht=tx&chl=c(n%2F2)%20%2B%20c(n%2F2)%20%3D%20cn不斷下去,我們會觀察到每一層所需的運行時間皆為https://chart.googleapis.com/chart?cht=tx&chl=c_n

在輸入規模大約30以上時,merge sort就要比insertion sort來的更快了。

參考資料: 合併排序法, Introduction to algorithms 3rd


上一篇
Day-5 演算法分析工具 : 漸進式符號(Big-O, Big-Theta, Big-Omega)
下一篇
Day-7 Divide-and-Conquer-2 : 求解遞迴式
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言