🐺

マージソートを実装してみる

に公開
Python 3
sort
アルゴリズム
mergesort
tech

アドベントカレンダー（自称）vol.2

皆さん、こんにちは。yumyum116 です。SWE転職を目指す者です。
アドベントカレンダーに便乗して、1日1記事投稿に挑戦するとともに、執筆活動の習慣化にも挑戦してみます。

この記事は、概念は理解できても、プログラムに起こすことが苦手な自分が綴る、概念を実装してみたシリーズです。
自分と同じようなところで躓いている方、プログラミング初学者の方の参考になれば嬉しいです。

今回は、効率的なソートアルゴリズムの一つとして知られる、マージソートを実装してみます。

1. マージソートとは

マージソートは、データ列を二分し、それぞれをマージソートした後、それらをマージすることを繰り返すことによって、データをソートするアルゴリズムです。

マージソートは、分割統治法という設計手法に基づきます。
分割統治法とは、大きな問題を、より小さな同種の部分問題に分割し、分割した部分問題を再帰的に解いた後に、その解を統合することにより、元の問題の解を得るアルゴリズム設計手法です。

この考え方自体は、色々な学問領域において応用されていますし、ビジネスの場面においても適用することのできる、汎用的な設計手法です。

ここでは、CS領域以外での適用例は脇において、プログラムに分割統治法の設計手法を適用することを考えてみます。

2. マージソートのアプローチ

ここに、配列 A = [4, 30, 5, 27, 9, 14, 1, 12, 22, 19] があるとします。
この配列を、分割統治法を適用して昇順にソートすることを考えます。

まず、配列 A を要素５番目までの配列 a_1 と６番目以降の配列 a_2 に分割します。
　a_1 = [4, 30, 5, 27, 9]
　a_2 = [14, 1, 12, 22, 19]

分割した配列を、さらに二分していきます。
　a_{11} = [4, 30]
　a_{12} = [5, 27, 9]
　a_{21} = [14, 1]
　a_{22} = [12, 22, 19]

この操作を、二分した部分配列の長さが 1 になるまで繰り返します。
ちなみに、この部分配列の長さが 1 になるまでの操作回数は、以下の式により表されます。

\frac{n}{2^k} = 1
k = log_2n

二分した部分配列の長さが 1 になったら、次は部分配列を統合することを考えます。
最終的には、昇順にソートした配列を得たいので、昇順にソートされた小さな部分配列をつくっていくことを考えます。

今、部分配列は次のようになっています。
[4]\quad[30]\quad[5]\quad[27]\quad[9]
[14]\quad[1]\quad[12]\quad[22]\quad[19]

ここから、まずは最小の部分配列を作ります。統合するときは、配列の各要素同士を比較して、値の小さい要素が、新しい配列に順番に格納されるようにします。
この操作で得られる部分配列は次のようになります。
[4, 30]\quad[5, 9, 27]
[1, 14]\quad[12, 19, 22]

元の配列と同じ長さになるまで、同じ操作を繰り返します。

２回目：
　　[4, 5, 9, 27, 30]
　　[1, 12, 14, 19, 22]
３回目：
　　[1, 4, 5, 9, 12, 15, 19, 22, 27, 30]

こうして、元の配列 A を昇順にソートすることができました。

ここで、部分配列を統合する際の要素の数は n です。したがって、部分配列の統合にかかるコストは n で済みます。

配列の分割回数は log_2n で表されるため、マージソートの時間計算量は、O(nlog_2n) で表されます。
隣接する要素同士を比較して、ソートするアルゴリズムの時間計算量は最悪の場合 O(n^2) となるため、マージソートを使うことで、より高速に配列をソートできます。

3. マージソートの実装例

さて、概念の説明を終えたところで、マージソートを実装してみます。

上記を踏まえると、①配列を部分配列に分割する関数と②部分配列を統合する関数の２つの関数で実装できそうです。

merge_sort.py
INF = 101

def merge(array, left, mid, right):
    left_array = array[left:mid]
    right_array = array[mid:right]

    left_array.append(INF)
    right_array.append(INF)

    left_index = 0
    right_index = 0
    for i in range(left, right):
        if left_array[left_index] < right_array[right_index]:
            array[i] = left_array[left_index]
            left_index += 1
        else:
            array[i] = right_array[right_index]
            right_index += 1

def merge_sort(array, left, right):
    if left + 1 >= right:
        return

    mid = (left + right) // 2
    merge_sort(array, left, mid)
    merge_sort(array, mid, right)
    merge(array, left, mid, right)

ここで、部分配列を統合する際に、部分配列の要素数が0になることを防ぐ目的で、要素の取りうる最大値より大きい値（番兵：INF）を、部分配列の末尾に追加する手法を採用しています。

これで、マージソートの実装は終わりです。

記事内に不適切な表現や、誤謬がある場合は修正します。
その際は、ご連絡いただけますと助かります。

それでは、また。

Discussion