今回は、Pythonの効率的なソートアルゴリズムであるMerge Sortについて見ていきます。
マージソートアルゴリズムは、既存のデータを昇順または降順で並べ替えるために使用されます。
このアルゴリズムをどのように利用し、Pythonで実装するかを見ていきましょう。
この記事もチェック：Pythonでストゥージソート(Stooge Sort)を実装する方法
Pythonでのマージソートの動作について
マージソートは、純粋に分割統治法に基づいた汎用的なソート技術です。
分割統治法では、要素はより小さな部分またはリストに分割されます。
そして、メインの入力リストのそれぞれの半分に適切な関数が適用されます。
さらに、その半分をマージして結果を得ます。
マージソートは「再帰的手法」であり，ソートされていない要素を2つに分割し，分割された要素に対して，関数が再帰的に呼び出されます．
この関数は，すべての要素が分割され，それ以上の分割が不可能になるまで，つまり，すべてのサブリストに 1 個の要素が含まれるようになるまで，半分またはサブリストに対して再帰的に呼び出しを行います．
次に、比較と交換という基本的な手法で要素がソートされます。
最後に、すべての要素をマージして、データ項目の最終的なソートリストを得ます。
PythonのMerge sortの動作を、例を使って理解しましょう。
要素のリストを考えてみましょう。
def merge_sort(inp_arr):
size = len(inp_arr)
if size > 1:
middle = size // 2
left_arr = inp_arr[:middle]
right_arr = inp_arr[middle:]
merge_sort(left_arr)
merge_sort(right_arr)
p = 0
q = 0
r = 0
left_size = len(left_arr)
right_size = len(right_arr)
while p < left_size and q < right_size:
if left_arr[p] < right_arr[q]:
inp_arr[r] = left_arr[p]
p += 1
else:
inp_arr[r] = right_arr[q]
q += 1
r += 1
while p < left_size:
inp_arr[r] = left_arr[p]
p += 1
r += 1
while q < right_size:
inp_arr[r]=right_arr[q]
q += 1
r += 1
inp_arr = [11, 31, 7, 41, 101, 56, 77, 2]
print("Input Array:)
print(inp_arr)
merge_sort(inp_arr)print("Sorted Array:)
print(inp_arr)
|
前述したように、まず元のデータリストを半分に分割します。
上記の元配列は8個の要素を持つので，これを4個の要素からなる部分配列に分割します．この配列は、各サブリストに1つの要素が入るまで、つまりそれ以上の分割ができなくなるまで、再帰的にサブリストに分割しつづけます。
Input Array:
[11, 31, 7, 41, 101, 56, 77, 2]
Sorted Array:
[2, 7, 11, 31, 41, 56, 77, 101]
|
このように、リストはすべての要素が1つになるまで再帰的に2つに分割されます。
分割後の各要素は次のようになります。
要素が分離されたら、要素を分割したときと同じ方法でデータ要素を結合する必要があります。
11と31という要素を考えてみましょう。
これらはソートされた位置にあるので、それらを結合して配列にマージします。
要素7と41もソートされた位置にあるので、同様にマージします。
次に、要素101と56について見てみると、それらの位置を入れ替えてマージする必要があります。
同様に、要素77と2についても、位置を入れ替えてマージします。
さらに進んで、2回目の反復では、2つの要素からなる部分配列と他の部分配列とを比較し、要素がソートされていることがわかれば、その部分配列を完全にマージします。
11,31]の部分配列は[7,41]と比較され、[56,101]の部分配列は[2,77]と比較されます。
データ項目がソート順でないため、それらの位置は入れ替わる。
3回目の反復では、4つの要素からなる部分配列が他の部分配列、すなわち、[7, 11, 31, 41] と [2, 56, 77, 101] とが比較されます。
明らかに見えるように、要素はソートされた位置にないので、最終的なソートされた配列を得るために、要素を交換し、結合します。
マージソートアルゴリズム
以下のステップを再帰的に実行することで、マージソートを行い、適切な結果を利用することができます。
- 元の配列を2つに分割するために必要な中間要素を見つけます。
- すべてのサブリストが単一の要素を含むまで、元のリストを再帰的に2つの半分に分割します。
- データ値をチェックし、ソートされていない順序で見つかった場合、要素を交換し、元のソートされたリストを得るためにサブリストをマージします。
Pythonでマージソートを実装する
結果は以下の通りです。
マージソートの時間計算量
マージソートの時間計算量は O(nlogn)
まとめ
この記事では、PythonのMergeソートの動作について理解しました。
Pythonの他のソートアルゴリズムも見てみましょう。