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