Python マージソート
マージソート（英語: Merge sort、または mergesort）は、マージ操作に基づいて考案された効率的なソートアルゴリズムです。このアルゴリズムは、分割統治法（Divide and Conquer）を採用した非常に典型的な応用例です。
分割統治法
- 分割：現在のシーケンスを再帰的に均等に半分へ分割します。
- 統合：要素の順序を保ちながら、前のステップで得られたサブシーケンスを1つに統合（マージ）します。
例
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r- m
# 一時配列を作成
L = [0] * (n1)
R = [0] * (n2)
# データを一時配列 L[] と R[] にコピー
for i in range(0 , n1):
L[i] = arr[l + i]
for j in range(0 , n2):
R[j] = arr[m + 1 + j]
# 一時配列を arr[l..r] にマージ
i = 0 # 最初のサブ配列のインデックスを初期化
j = 0 # 2番目のサブ配列のインデックスを初期化
k = l # マージするサブ配列のインデックスを初期化
while i < n1 and j < n2 :
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# L[] の残りの要素をコピー
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# R[] の残りの要素をコピー
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def mergeSort(arr,l,r):
if l < r:
m = int((l+(r-1))/2)
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print ("指定された配列")
for i in range(n):
print ("%d" %arr[i]),
mergeSort(arr,0,n-1)
print ("\n\nソート後の配列")
for i in range(n):
print ("%d" %arr[i]),
上記のコードを実行すると、出力結果は次のとおりです。
给定的数组 12 11 13 5 6 7 排序后的数组 5 6 7 11 12 13その他の拡張