読者です 読者をやめる 読者になる 読者になる

A社の佐伯さんがのらりくらりと

A社の佐伯さんがのらりくらりと。インターネットと少しだけ生活のこと。

【アルゴリズムの勉強】Pythonでマージソートを書いてみた

学習エントリ。

Pythonマージソートを実装する。

マージソートってなんぞ

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする[1]。
(ナイーブな)クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。

マージソート - Wikipedia

example_list = [5,2,10,1,18,3,7,4]
ASC, DESC = 1, 2

def mergeSort(list,order):   
    mid = len(list)
    if mid > 1:
        left = mergeSort(list[:(mid/2)],order)           
        right = mergeSort(list[(mid/2):],order)
        list = []
        while len(left) != 0 and len(right) != 0: 
            if order == ASC:
                if left[0] < right[0]:                
                    list.append(left.pop(0))
                else:                                  
                    list.append(right.pop(0))
            elif order == DESC:
                if left[0] > right[0]:                
                    list.append(left.pop(0))
                else:                                  
                    list.append(right.pop(0))
        if len(left) != 0:                        
            list.extend(left)                     
        elif len(right) != 0:                   
            list.extend(right)               
    return list         


        

print("ASC is...")
print(mergeSort(example_list,ASC)) #[1, 2, 3, 4, 5, 7, 10, 18]
print("DESC is...")
print(mergeSort(example_list,DESC)) #[18, 10, 7, 5, 4, 3, 2, 1]
ポイントっぽいところ

再帰的に最小までスライシングした配列を作る
・初期化したlistにleft[0],right[0]の小さい方を加えていく
・※その際popを使うことで元の要素を減らしていくどちらかの要素数が0になるまで行う
・どちらかの要素数が0になった場合、反対の要素数は1残ってしまうので、その配列を最後に足してあげる