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

设计演算法

我们可以选择的演算法设计技术有很多种。插入排序使用了递增逼近(incremental approach)的方法 : 在排序子阵列之後，将单个元素插入子阵列的适当位置，产生出完成排列的子阵列。

分治法(Divide-and-Conquer)

有许多演算法使用了递回的结构进行设计 : 为了解决一个问题，将问题拆分後经过多次递回解决问题的子问题，最终合并结果并解决问题。这种演算法就是分治法的想法。分治法在每一层的递回会有三个步骤:

• 分解(Divide) : 将原问题分解成许多个子问题，每一个子问题都是原问题规模较小的实例。
• 解决(Conquer) : 递回的方式去求解各子问题，当子问题的规模够小时，则直接求解。
• 合并(Combine) : 将子问题的解合并成原问题的解。

合并排序法(merge sort)

合并排序法(merge sort)就是一种由分治法实现的演算法，直观上也是符合分治法的三个步骤

• 分解(Divide) : 分解待排序长度为的阵列，变成长度为长度的两个子阵列。
• 解决(Conquer) : 使用合并排序法递回的排序两个子阵列。
• 合并(Combine) : 合并两个已经排序的子阵列产生出已经完成排序的原阵列。

当子阵列的长度为1时，表示子阵列已经完成排序，并开始合并去完成排序每一个子阵列。

合并排序法关键的操作步骤为'合并'，将两个以排序的子阵列合并。我们通过MERGE(A, p, q, r)来完成合并，A为阵列，为阵列的下标，满足。在合并的过程中，我们假设子阵列和都已经完成排序。将这两个子阵列合并形成新的一个已经完成排序，规模更大的子阵列，并替换掉目前的子阵列。

合并的过程大约需要Θ的时间，其中是整个待排序阵列的元素个数。整个合并大概会执行以下操作。想像桌上有两堆牌面朝上的扑克牌，每一堆都已经完成排序，最小的牌在每一堆的最上面。我们希望把这两堆牌合并成单一已经排好序的扑克牌堆，并且完成之後牌面向下放在桌上。

来源

我们的操作为在牌面朝上的两堆牌上选取最上面那一张，在这两张牌中选出最小的那一张牌，把这张牌从刚刚的扑克牌堆移除，将这张牌牌面向下放置在桌上另外的位置，成为新的扑克牌堆，我们称这一个堆为输出堆。不断重复这个步骤，直到有一堆扑克牌堆没有扑克牌为止，这时候，我们只要拿起剩下一开始的扑克牌堆并将牌面向下放置到输出堆。因为每一次我们只比较两个扑克牌堆最上面的那张牌，计算每一个步骤都需要常数时间。最多执行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)表示。

进入回圈迭代，比较和，发现，因此将R[0]放入A阵列中，并将R的index j往後走一格，表示1已经放入A阵列中，A阵列的index k也往後走一格，如图(b)所示。

不断进入迭代，进行比较後放入A阵列中，如果其中一个子阵列碰到无限大，则表示该阵列所有元素已经放入A阵列中。

整个MERGE具体的执行过程如下:

• 第1行表示子阵列的长度。
• 第2行表示子阵列的长度。
• 第3行宣告长度分别为和的阵列L和R，每个阵列保留多1的长度是为了放入哨兵牌。
• 第4行到第5行的for回圈将子阵列复制到。
• 第6行到第7行的for回圈将子阵列复制到。
• 第8行到第9行将哨兵放入阵列L和R的末端
• 第10行到第17行经过循环不变式，执行个基本步骤:
• • 在开始第12行到第17行for回圈的每一次迭代，子阵列按照从小到大排序，包含和中个最小元素，得出和是各自在阵列中还没被复制回A阵列的最小元素。

我们需要证明第12行到第17行for回圈的第一次迭代之前循环不变式成立，每一次迭代之前也成立，最後一次迭代结束後也成立。这个循环不变式提供某些性质帮助我们证明正确性。

• 初始化 : 在第一次迭代之前，for的初始条件，所以为空。这个空的子阵列里面包含L和R的个最小元素，又因为，所以和都是各自所在的阵列中未被复制到A阵列的最小元素。

• 保持 : 我们假设。这时候，是没有放回A阵列的最小元素，子阵列包含个最小元素。在for中增加k值和i值，为了下次迭代重新建立了该循环不变式。若，则第16到17行执行适当的操作来维持循环不变式。

• 终止 : 终止时。根据循环不变式，子阵列就是由小到大排序，且包含和中个最小元素。阵列L和R一起包含个元素。除两个哨兵元素外，其他元素都已经放入A阵列中。

我们已知，第1到3行和第8到11行每一行都需要常数时间，第4到7行的for回圈需要ΘΘ的时间，第12行到17行的for回圈有n次迭代，每一次迭代也需要常数时间。

MERGE-SORT的主要想法，就是将两个子阵列MERGE-SORT之後，在MERGE起来，会将猜分成两个子阵列和，前者和後者均有个元素。

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)

不断将阵列拆分成两个子阵列，之後再作合并

合并排序在上进行操作，不断地向上推进，合并以排序的子阵列。

以下为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);
    }
}

C语言实作

void merge(int *arr, int head, int mid, int tail)
{
    int lenA = mid - head + 1;
    int lenB = tail - (mid + 1) + 1;
    int *leftSub = (int*)malloc(sizeof(int) * lenA);
    int *rightSub = (int*)malloc(sizeof(int) * lenB);
    leftSub[lenA - 1] = INT_MAX;
    rightSub[lenB - 1] = INT_MAX;

    int leftIndex = 0;
    int rightIndex = 0;

    for (leftIndex = 0; leftIndex < lenA; leftIndex++)
    {
        leftSub[leftIndex] = arr[head + leftIndex]; 
    }
    for (rightIndex = 0; rightIndex < lenB; rightIndex++)
    {
        rightSub[rightIndex] = arr[mid + 1 + rightIndex]; 
    }

    
    leftIndex = 0;
    rightIndex = 0;
    int writePointer = head;
    
    while (leftIndex < lenA && rightIndex < lenB)
    {
        if (leftSub[leftIndex] < rightSub[rightIndex])
        {
            arr[writePointer] = leftSub[leftIndex];
            leftIndex++;
        }
        else
        {
            arr[writePointer] = rightSub[rightIndex];
            rightIndex++;
        }
        writePointer++;
    }

    while (leftIndex < lenA)
    {
        arr[writePointer] = leftSub[leftIndex];
        leftIndex++;
        writePointer++;
    }

    while (rightIndex < lenB)
    {
        arr[writePointer] = rightSub[rightIndex];
        rightIndex++;
        writePointer++;
    }
}

void mergeSort(int *arr, int head, int tail)
{
    if (head < tail)
    {
        int mid = (head + tail) / 2;
        mergeSort(arr, head, mid);
        mergeSort(arr, mid + 1, tail);
        merge(arr, head, mid, tail);
    }
}

分析分治演算法

当一个演算法包含呼叫自身递回时，我们会使用递回关系式去描述他所花费的时间。

分治法运行时间的递回关系式来自分解，合并，解决这三个步骤。假设为规模为n的一个问题所需要的运行时间。如果问题的规模足够小时，如对某个常数，，则直接求解即需要常数时间，我们用 Θ表示。假设我们将原问题分解成个子问题，每一个子问题的规模都是原问题的(对於合并排序来说，a和b皆为2)。为了求解一个规模为的子问题，需要的时间，所以需要的时间来解决个子问题。如果将原问题拆分成多个子问题需要的时间，合并多个子问题的解成为原问题的解需要的时间，那麽得到以下递回关系式 :

合并排序分析

虽然合并排序在输入阵列不是偶数也同样可以作用，但是，假定原问题的规模是，那麽我们可以对递回式的分析进行简化。每一步的分解都会刚好产生出的两个子阵列。其实我们这样的假设不会影响到递回式的量级，後续会详细说明。

下面我们分析建立合并排序n个数的最坏情况的运行时间的递回式。合并排序一个元素需要常数时间。当有个元素时，我们分解运行时间如下:

• 分解 : 分解步骤仅需要知道子阵列的中间位置，需要常数时间，因此Θ
• 解决 : 递回的求解两个规模均为的子问题，需要的时间
• 合并 : 具有n个元素的子阵列MERGE过程需要Θ的时间，所以Θ

当为了分析合并排序的运行时间而将和函数相加时，我们是把一个函数Θ和另一个Θ函数相加。得出来的结果是一个n的线性函数，也就是Θ，再将这个函数和解决的部分相加，得到以下最差运行时间的递回关系式

常数代表合并排序规模为1的问题所需要的时间。

下图展示了如何求解递回式，假设刚好为。
(a)部分展示
(b)部分展示一棵被扩展成描述递回式的树。表示树根(递回的最顶层)，根的两个子树为较小的递回式
(c)部分展示再被拆解的过程。在第二层的递回中，两个子节点中所需的运行时间为，不断分截直到规模下降到1
(d)部分展示了整个递回树，并推出结果

高度为，总共有层，整体时间为(表示)，表示为Θ

我们将每一层所需要的运行时间相加，顶层为，下一层为不断下去，我们会观察到每一层所需的运行时间皆为。

在输入规模大约30以上时，merge sort就要比insertion sort来的更快了。

参考资料: 合并排序法, Introduction to algorithms 3rd