Pythonでマージソートを書いてみたメモ
マージソートについて自分用にメモを書いてみました。
マージソートとは
- 分割統治法に基づく高速なソートアルゴリズムで、大きなデータサイズに対応できる。
- 計算量は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]
- 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種を可視化してみた
Author And Source
この問題について(Pythonでマージソートを書いてみたメモ), 我々は、より多くの情報をここで見つけました https://qiita.com/rA9-S/items/6d94b1619907d0ffa0b5著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .