マージソートについて
- 計算量はO(nlogn)
- 大容量のデータにも使える
- リストの各要素を新しいリストとしてバラバラにした後で統合していく
- 統合は2つのリストを使って行うことを繰り返す
- 統合時は各リストの先頭の要素を大小比較し、小さい方を取り出すことを繰り返す
コード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
data = [4,7,1,3,9,2,8,5,10,6] def merge_sort(data): #[1] if len(data) <= 1: #[2] return data #[2] mid = len(data)//2 #[3] left = merge_sort(data[:mid]) #[4] right = merge_sort(data[mid:]) #[4] return merge(left,right) #[5] def merge(left,right): result = [] i,j = 0,0 while (i < len(left)) and (j < len(right)): #left,rightのリストの要素数よりもi,jがそれぞれ小さい場合 if left[i] <= right[j]: #[6]i番目のleftの要素よりもj番目のrightの要素が大きい場合 result.append(left[i]) #left[i]をresultに追加 i += 1 else: #i番目のleftの要素がj番目のrightの要素よりも大きい場合 result.append(right[j]) #right[j]をresultに追加 j += 1 if i < len(left): #iがleftの要素数よりも小さければ result.extend(left[i:]) #i番目よりも後をresultに結合 if j < len(right): #iがrightの要素数よりも小さければ result.extend(right[j:]) #j番目よりも後をresultに結合 return result print(merge_sort(data))り |
[1]merge_sort関数
引数として受け取ったリストの要素数が1以下の場合はそのままリストを返します。[2]
リストの中央のインデックスをmidに代入します。[3]
中央から左のリストと中央から右側のリストに対して、同じことを繰り返します。[4]
merge関数を呼び出します。[5]
参考
こちらの書籍を参考にしています。
一度バラバラに分解してから統合していく様子を図にして解説しています。
また、左右に分割したリストについて、それぞれの先頭を比較して取り出す点についても触れられています。
どちらも、直感的にわかりやすい説明になっているので、チェックしてみるとより理解が深まるかと思います。
コメント