本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、配列によるマージソート(Merge Sort)について学んでいきます。
マージソートとは
マージソート(Merge Sort)は、前回学んだクイックソートと同じの計算量を誇る速いアルゴリズムですが、定数係数が大きいためクイックソートよりは遅いアルゴリズムになります。
マージソートでも、クイックソートで用いた分割統治(Divide and Rule or Divide and Conquer)というアプローチ方法で部分的に分けてから、マージ(併合)して整列を行います。
以下がマージソートを行う過程を簡略化したものになります。
マージソートでは、配列をずつ分割していき、シーケンシャルに要素へアクセスしていきます。
そして、最終的に一つの要素になるまで再帰呼び出しをし、要素を分割できないまで進んだら、要素をマージしながら整列をさせていきます。
またマージソートには配列によるものと連結リストによるものがあり、今回は配列によるものを作成します。
配列によるものでは、マージした結果を保存するために別途入力データと同じサイズの配列を用意しなければならないため、その分記憶領域が必要となります。
この作業用の領域を確保しない方法もあるようですが、その分の計算量が別途必要になってきます。
なお、マージソートは安定な整列アルゴリズム(データの位置関係が保存される)になります。
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データとして保存しておき、これをロードします。
自環境で実行した結果を以下にまとめます。
アルゴリズム名 | 所要時間(秒) |
---|---|
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 |
これまで作成した整列アルゴリズムの中では二番目に速い結果となりました。
マージソートのポイントとしては、前半と後半を作業用のリストにコピーする際に、後半のほうを逆順でコピーしていくことで、マージするときの境界ができることです。