マージソートについて自分用にメモを書いてみました。
マージソートとは
- 分割統治法に基づく高速なソートアルゴリズムで、大きなデータサイズに対応できる。
- 計算量はO(nlogn)
- logn個の階層があり、各層ごとの計算量はO(n)であるため。
- ソートしても同じ値の順序が変わることのない安定なソート
- 一時的にデータを保存するメモリが必要
コード
marge_sort.py
def merge(A, left, mid, right):
L = []
for i in range(mid - left):
L.append(A[left + i])
L.append(1000) # 必ずソートする数よりも大きい数にする
R = []
for i in range(right - mid):
R.append(A[mid + i])
R.append(1000) # 必ずソートする数よりも大きい数にする
i = j = 0
for k in range(left, right):
if L[i] <= R[j]:
A[k] = L[i]
i += 1
else:
A[k] = R[j]
j += 1
def merge_sort(A, left, right):
if left+1 < right:
mid = (left + right) // 2
merge_sort(A, left, mid)
merge_sort(A, mid, right)
merge(A, left, mid, right)
return A
print(merge_sort([3, 1, 10, 2.5, 11, 3, 21, 4, -1], 0, 9))
# [-1, 1, 2.5, 3, 3, 4, 10, 11, 21]
今回は1000以下の数を昇順にソートできる
1000は適当に定めたので、大きくすればもっと大きな数でもソートできる
総呼び出し回数をうまくかけなかった…
参考
C言語でマージソート
ソートアルゴリズムと Python での実装
【Unity】ソートアルゴリズム12種を可視化してみた