4月 10, 2010

【演算】合併排序法 - Mergesort

@
  合併排序法(mergesort)是一個典型利用分治法(divide and conquer,D&C)解決問題的例子。其原理為不斷地將資料分成兩等分,直到每份的資料量小到一個程度後,各自排序後再一一合併起來。



  假設現在有 n 筆資料需要進行排序。

  則我們首先會將這 n 筆資料分成兩等分(大小皆為 n/2);接著,再將這兩堆大小為 n/2 的資料各自分為兩等分(大小皆為 n/4);同樣的,我們再將這四堆大小為 n/4 的資料各自分為兩等分(大小皆為 n/8)。

  如此進行下去,直到每堆的資料量足夠小(例如:每堆只剩 1 筆資料)之後,我們就分別將每堆資料進行排序,再將這些資料堆兩兩一對進行合併,直到排序完成為止。





  其虛擬碼大致如下:

Function mergeSort(Type data[1..n])
    If n <= 1 then return

    Index x, y, i, j
    x = n / 2
    y = n - x

    Type left[1..x], right[1..y]
    For i from 1 to x do
        left[i] = data[i]
    For i from 1 to y do
        right[i] = data[x + i]

    mergeSort(left)
    mergeSort(right)
    merge(data, left, right)
End

Function merge(Type data[1..n], Type left[1..x], Type right[1..y])
    Index i, j, k
    i = j = k = 1

    While i <= x and j <= y do
        If left[i] < right[j] then
            data[k] = left[i]
            i = i + 1
        Else
            data[k] = right[j]
            j = j + 1
        k = k + 1

    While i <= x do
        data[k] = left[i]
        i = i + 1
        k = k + 1

    While j <= y do
        data[k] = right[j]
        j = j + 1
        k = k + 1
End



  讓我們舉個實際的例子說明:現在我們有八筆資料需要排序(由小而大):

(84、13、73、26、32、19、91、38)

  且只要每堆的資料量大於 1 時,就需要再將資料進行分割。

  首先,我們先將資料分成兩等分:

(84、13、73、26) (32、19、91、38)

  此時每堆的資料量為 4 (8 / 2) > 1。因此,我們還需要將每堆資料再各自分成兩等分:

(84、13) (73、26) (32、19) (91、38)

  此時每堆的資料量為 2 (4 / 2) > 1。再一次,我們將每堆資料各自分成兩等分:

(13) (84) (26) (73) (19) (32) (38) (91)

  此時每堆的資料量為 1 (2 / 2) = 1 ,符合停止切割的條件。所以接下來,我們要將資料兩兩合併。在合併的同時,同時確保資料排序:

(13、84) (26、73) (19、32) (38、91)

  同樣的,我們將資料兩兩合併:

(13、26、73、84) (19、32、38、91)

  同樣的,我們將資料兩兩合併:

(13、19、26、32、38、73、84、91)



  最後,我們從時間效率上來討論合併排序法。設 merge sort 的時間複雜度函數為 T(n)。

  我們可以知道,在每一次呼叫 mergeSort() 函式時,我們都需要分別將前半段與後半段的資料複製給 left 跟 right,所以複製資料的時間花費為 c1n。

  然後,我們需要遞迴呼叫兩次資料大小為 n/2 的 mergeSort(),時間花費為 2T(n / 2)。最後再加上呼叫 merge() 函式所需的時間花費 c2n。所以我們可以得到:T(n) = 2T(n / 2) + cn (n > 1),且 T(1) = 1。



  若是將式子展開:T(n) = 2T(n / 2) + cn = 4T(n / 4) + 2c(n / 2) + cn = 8T(n / 8) + 4c(n / 4) + 2c(n / 2) + cn = ... = cn + cn + cn + ... + cn = cn(lg n + 1) ∈ O(n lg n)(註1)。

  由此可見,合併排序的的時間效率是相當不錯的。



  另外,因為有網友詢問非遞迴的合併排序法,因此試著寫了以下這個虛擬碼:

Function mergeSort(Type data[1..n])
    If n <= 1 then return

    Index i, j, k
    For i from 2 to (n / 2) do
        For j from 0 to (n - 1) step (2 * i) do
            Index x, y
            x = min(i, n - j)
            y = min(i, max(0, n - i - j))

            Type left[1..x], right[1..y]
            For k from 1 to x do
                left[k] = data[j + k]
            For k from 1 to y do
                right[k] = data[i + j + k]

            Index p, q, r
            p = q = 1
            r = j
            While p <= x and q <= y do
                If left[p] < right[q] then
                    data[r] = left[p]
                    p = p + 1
                Else
                    data[r] = right[q]
                    q = q + 1
                r = r + 1

            While p <= x do
                data[r] = left[p]
                p = p + 1
                r = r + 1

            While q <= y do
                data[r] = right[q]
                q = q + 1
                r = r + 1
End

  寫起來感覺不太直觀,如果有錯誤歡迎糾正我:)


註1. 其實可以直接利用支配定理(Master theorem)來求出複雜度 T(n)。

12 回覆:

匿名 提到...

您好,想請問在 merge () 這涵式中

if (left[i] < right[j])
是否要改成
if (left[i] <= right[j])
才能達到 merge sort 中的 stable 特性?

感謝您的回答~

小參 提到...

是的,您說的沒錯。

原始資料中,前端的資料會被分進 left[], 而後端的資料會被分進 right[]。
所以,在 left[i] = right[j] 的情況下,應該要將 left[i] 放在 right[j] 的前端。
如此,才能達到不破壞等值紀錄原始相對順序的 stable 特性。

感謝您的補充。

匿名 提到...

This code is incorrect.

In the function "merge()",

you should put
while (i < x && j < y)
instead of
while (i <= x && j <= y)

and same with others

小參 提到...

OK, thanks you :)

匿名 提到...

請問
如果不用遞迴的方式做的話
該如何執行merge?

匿名 提到...

樓上是台科大鮑興國教授演算法課的學生吧?

小參 提到...

你好
不好意思, 這麼久才回覆
非遞迴的 mergesort 版本我已經更新在文章上了:)

鄭旭峰 提到...

大大 請問跑出來可以跑嗎????怎麼會出現bug

匿名 提到...

謝謝大大分享

匿名 提到...

請問step是什麼意思

Allen Chen 提到...

非遞迴的虛擬碼, 在陣列中有奇數個數的時候似乎會有問題
不過我不肯定是不是我自己有錯, 我是用C++寫的, 因此index是改由0開始

Allen Chen 提到...

https://c2.staticflickr.com/8/7186/26884313321_91116fd0cc_o.png
這是我實際跑出來的情形, 看起來應該是沒有寫錯

張貼留言