[…] […] […]
マージソート
T
実装
整数の配列（一般的にソートを導入するために使用される）とカスタムオブジェクト（より実用的で現実的なシナリオ）の2種類のコレクションに対して Merge Sort を実装することにする。
Merge Sort アルゴリズムをトップダウン方式で実装する。アルゴリズムはあまり「きれい」に見えず、混乱する可能性があるので、各ステップを詳細に説明する。
配列の並べ替え
まず、簡単なところから始めましょう。このアルゴリズムの基本的な考え方は，（部分）配列を半分に分割し，再帰的にソートすることです．これを可能な限り、つまり要素が1つしかない部分配列ができるまで続けたいと思います。
def merge_sort(array, left_index, right_index):
if left_index >= right_index:
return
middle = (left_index + right_index)//2
merge_sort(array, left_index, middle)
merge_sort(array, middle + 1, right_index)
merge(array, left_index, right_index, middle)
最後に merge メソッドを呼び出すことで、ソートを開始する前にすべての分割が行われるようにします。また、 // 演算子を使用して、インデックスに整数値が必要であることを明示的に示しています。
次のステップでは、いくつかのステップとシナリオを通して、実際にマージする部分です。
- 配列のコピーを作成します。最初の配列は
[left_index,...,middle]の部分配列で、2番目の配列は[middle+1,...,right_index]の部分配列です。 - 両方のコピーを調べて（両方の配列のポインタを追跡して），現在見ている 2 つの要素のうち小さい方を選び，それらをソートされた配列に追加します．どちらの配列から要素を選んでも、ソートされた配列の前方に進みます。
- もし片方のコピーの要素がなくなったら、もう片方のコピーの残りの要素をソート済みの配列に追加するだけです。
要件を整理したところで、次に merge() 関数を定義してみましょう。
def merge(array, left_index, right_index, middle):
# Make copies of both arrays we're trying to merge
# The second parameter is non-inclusive, so we have to increase by 1
left_copy = array[left_index:middle + 1]
right_copy = array[middle+1:right_index+1]
# Initial values for variables that we use to keep
# track of where we are in each array
left_copy_index = 0
right_copy_index = 0
sorted_index = left_index
# Go through both copies until we run out of elements in one
while left_copy_index < len(left_copy) and right_copy_index < len(right_copy):
# If our left_copy has the smaller element, put it in the sorted
# part and then move forward in left_copy (by increasing the pointer)
if left_copy[left_copy_index] <= right_copy[right_copy_index]:
array[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
# Opposite from above
else:
array[sorted_index] = right_copy[right_copy_index]
right_copy_index = right_copy_index + 1
# Regardless of where we got our element from
# move forward in the sorted part
sorted_index = sorted_index + 1
# We ran out of elements either in left_copy or right_copy
# so we will go through the remaining elements and add them
while left_copy_index < len(left_copy):
array[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
sorted_index = sorted_index + 1
while right_copy_index < len(right_copy):
array[sorted_index] = right_copy[right_copy_index]
right_copy_index = right_copy_index + 1
sorted_index = sorted_index + 1
では、このプログラムをテストしてみましょう。
array = [33, 42, 9, 37, 8, 47, 5, 29, 49, 31, 4, 48, 16, 22, 26]
merge_sort(array, 0, len(array) -1)
print(array)
そして、その出力は
[4, 5, 8, 9, 16, 22, 26, 29, 31, 33, 37, 42, 47, 48, 49]
カスタムオブジェクトの並べ替え
カスタムオブジェクトのソート
基本的なアルゴリズムは理解できたので、次はカスタムクラスをどのようにソートするか見てみましょう。必要に応じて __eq__、__le__、__ge__ などの演算子をオーバーライドすることができます。
この場合、上記と同じアルゴリズムを使用できますが、カスタムオブジェクトをソートする方法が1つに限定され、ほとんどの場合、望んだものではありません。より良いアイデアは、アルゴリズム自体をより汎用的なものにし、代わりに比較関数を渡すことです。
まず、カスタムクラスである Car を実装し、いくつかのフィールドを追加してみましょう。
class Car:
def __init__(self, make, model, year):
self.make = make
self.model = model
self.year = year
def __str__(self):
return str.format("Make: {}, Model: {}, Year: {}", self.make, self.model, self.year)
それから Merge Sort メソッドに少し変更を加えます。欲しいものを実現する最も簡単な方法は、ラムダ関数を使うことです。パラメータを追加してメソッドの呼び出しを変更し、さらに1行のコードを追加するだけで、このアルゴリズムがより汎用的なものになるのがわかると思います。
def merge(array, left_index, right_index, middle, comparison_function):
left_copy = array[left_index:middle + 1]
right_copy = array[middle+1:right_index+1]
left_copy_index = 0
right_copy_index = 0
sorted_index = left_index
while left_copy_index < len(left_copy) and right_copy_index < len(right_copy):
# We use the comparison_function instead of a simple comparison operator
if comparison_function(left_copy[left_copy_index], right_copy[right_copy_index]):
array[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
else:
array[sorted_index] = right_copy[right_copy_index]
right_copy_index = right_copy_index + 1
sorted_index = sorted_index + 1
while left_copy_index < len(left_copy):
array[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
sorted_index = sorted_index + 1
while right_copy_index < len(right_copy):
array[sorted_index] = right_copy[right_copy_index]
right_copy_index = right_copy_index + 1
sorted_index = sorted_index + 1
def merge_sort(array, left_index, right_index, comparison_function):
if left_index >= right_index:
return
middle = (left_index + right_index)//2
merge_sort(array, left_index, middle, comparison_function)
merge_sort(array, middle + 1, right_index, comparison_function)
merge(array, left_index, right_index, middle, comparison_function)
それでは、変更したアルゴリズムをいくつかの Car インスタンスでテストしてみましょう。
car1 = Car("Alfa Romeo", "33 SportWagon", 1988)
car2 = Car("Chevrolet", "Cruze Hatchback", 2011)
car3 = Car("Corvette", "C6 Couple", 2004)
car4 = Car("Cadillac", "Seville Sedan", 1995)
array = [car1, car2, car3, car4]
merge_sort(array, 0, len(array) -1, lambda carA, carB: carA.year < carB.year)
print("Cars sorted by year:")
for car in array:
print(car)
print()
merge_sort(array, 0, len(array) -1, lambda carA, carB: carA.make < carB.make)
print("Cars sorted by make:")
for car in array:
print(car)
出力が得られる。
Cars sorted by year:
Make: Alfa Romeo, Model: 33 SportWagon, Year: 1988
Make: Cadillac, Model: Seville Sedan, Year: 1995
Make: Corvette, Model: C6 Couple, Year: 2004
Make: Chevrolet, Model: Cruze Hatchback, Year: 2011
Cars sorted by make:
Make: Alfa Romeo, Model: 33 SportWagon, Year: 1988
Make: Cadillac, Model: Seville Sedan, Year: 1995
Make: Chevrolet, Model: Cruze Hatchback, Year: 2011
Make: Corvette, Model: C6 Couple, Year: 2004
結論
マージソートは効率的で汎用的なソートアルゴリズムです。主な利点はアルゴリズムの信頼性の高い実行時間と、大きな配列をソートする際の効率性です。クイックソートとは異なり、実行時間の悪化につながるような不幸な判断に依存することはありません。
主な欠点は、マージソートがマージする前に配列の一時的なコピーを保存するために使用する追加のメモリである。しかし、Merge Sortは将来のソフトウェア技術者にアルゴリズムを作成するための分割統治アプローチを紹介するための、直感的で優れた例である。
我々は、単純な整数配列と、比較に使用するラムダ関数によるカスタムオブジェクトの両方に対してマージソートを実装した。最後に、両方のアプローチで可能な最適化について簡単に議論した。