Engineering Note

プログラミングなどの技術的なメモ

マージソート(配列) (Pythonによるアルゴリズムとデータ構造)

merge sort

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonアルゴリズムとデータ構造について学習していきます。

今回は、配列によるマージソート(Merge Sort)について学んでいきます。

 

 

マージソートとは

マージソート(Merge Sort)は、前回学んだクイックソートと同じO(n \log n)の計算量を誇る速いアルゴリズムですが、定数係数が大きいためクイックソートよりは遅いアルゴリズムになります。

マージソートでも、クイックソートで用いた分割統治(Divide and Rule or Divide and Conquer)というアプローチ方法で部分的に分けてから、マージ(併合)して整列を行います。

以下がマージソートを行う過程を簡略化したものになります。

 

fig1. マージソートの過程

fig1. マージソートの過程

 

マージソートでは、配列を\frac{1}{2}ずつ分割していき、シーケンシャルに要素へアクセスしていきます。

そして、最終的に一つの要素になるまで再帰呼び出しをし、要素を分割できないまで進んだら、要素をマージしながら整列をさせていきます。

またマージソートには配列によるものと連結リストによるものがあり、今回は配列によるものを作成します。

配列によるものでは、マージした結果を保存するために別途入力データと同じサイズの配列を用意しなければならないため、その分記憶領域が必要となります。

この作業用の領域を確保しない方法もあるようですが、その分O(n)の計算量が別途必要になってきます。

なお、マージソート安定な整列アルゴリズム(データの位置関係が保存される)になります。

 

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

それでは、Pythonマージソートを実装してみます。 

 

# merge_sort.py
import time
import pickle

def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1
            
with open('sample_data.pkl', 'rb') as f:
    lst = pickle.load(f)

MAX_ELEMENTS = len(lst)
tmp_array = [None for _ in range(MAX_ELEMENTS)]

start = time.time()
merge_sort(lst, 0, len(lst)-1)
print("elapsed {} sec".format(time.time() - start))

 

動作確認

それでは上記で作成したスクリプトを実行してみます。

事前に1~20,000までの値からランダムに20,000個生成したリストをpickleデータとして保存しておき、これをロードします。

自環境で実行した結果を以下にまとめます。

 

データ20,000個を整列した結果一覧
アルゴリズム 所要時間(秒)
Python 組込みメソッド(sort()) 0.015
Bubble Sort 72.979
Selection Sort 17.747
Insertion Sort 41.236
Shell Sort 0.253
Quick Sort 0.084
Merge Sort 0.168

 

これまで作成した整列アルゴリズムの中では二番目に速い結果となりました。

マージソートのポイントとしては、前半と後半を作業用のリストにコピーする際に、後半のほうを逆順でコピーしていくことで、マージするときの境界ができることです。

 

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)