再帰を使ったマージソートのやり方
※備忘録的な感じ (見返す時に忘れている・コードだけでは理解ができない等があると思うので）
配列data = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]
1. 配列の真ん中でleft(左）・right(右）に分ける => 左[3,1,9,4,2] 右[5,7,6,8,10] 真ん中: 5
2. left・rightでそれぞれでさらに分けていく(再帰を使う） => 左[3,1,9,4,2] -> 左[3,1] 右[9,4,2] 真ん中: 2
右[5,7,6,8,10] -> 左[5,7] 右[6,8,10]....のように分けていく
3.最終的に[3],[1],[9],[4],[2],[5],[7],[6],[8],[10] となる（下準備完了！）
4.今度は、二分割した値を左（０から始まるため）から順番新しい変数（result_sortに並び替え結果を代入していく(結合)。[3,1],[4,2] => それぞれソートを行う [1,3][2,4]
※ [9],[6]がない！なぜ？ => [9,4,2]を分けるとき 真ん中が「１」のため 右:[9] 左: [4,2]となってしまうため先に[4,2]から処理をしてしまう。（再帰は、1->2->3->4->5 と進めた後, 5->4->3->2->1と巻き戻しをしながら処理を戻していく） => より理解を深めるためには、再帰の勉強をする
5.[9]と[4,2]は ->[9]と[4,2]で並び替え -> result_sort => [2,4,9]となる
6.[3,1]と[9,4,2]は -> [3,1]と[9,4,2]で並び替え -> result_sort => [1,2,3,4,9]
7.右が完了。次は左から 4~6 を行う
8 [3,1,9,4,2] と 右[5,7,6,8,10] を比較して行う
9 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] となる
コードでの解説(python)
data = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]
データを変数に代入
def merge_sort(data):
if len(data) <= 1: #配列の中身が1以下になったらtrue
return data
center = len(data) // 2 #配列の中心
left = merge_sort(data[:center])#左側に分断 [3,1,9,4,2] => [3,1] => [3]
right = merge_sort(data[center:]) #右側に分断 [5,7,6,8,10] => [9,4,2] => [1]
return left, right #=> [3], [1]が渡される
1 ~ 3 をこのコードで行う事ができる。
def merge_sort(data):
if len(data) <= 1: #配列の中身が1以下になったらtrue
return data
center = len(data) // 2 #配列の中心
left = merge_sort(data[:center])#左側に分断 [3,1,9,4,2] => [3,1] => [3]
right = merge_sort(data[center:]) #右側に分断 [5,7,6,8,10] => [9,4,2] => [1]
return merge(left, right)
return merge(left, right)を加えただけ
def merge(left, right):
result_sort = [] #結合結果
left_i, right_j = 0, 0
print(left + right) #=> 並び替えをしようとする配列がわかる
while(left_i < len(left)) and (right_j < len(right)):
if left[left_i] <= right[right_j]:
result_sort.append(left[left_i]) #ここで結合をしようとしている rightとleftを比較しながらresultに当てていく
left_i += 1
else:
result_sort.append(right[right_j]) #ここで結合をしようとしている rightとleftを比較しながらresultに当てていく
right_j += 1
if len(left[left_i:]) != 0: #=> 並び替えをしたが余ってしまったleftの配列内の数字が0で無ければTrue(left_iで確認）
result_sort.extend(left[left_i:])
if len(right[right_j:]) != 0:
result_sort.extend(right[right_j:]) #並び替えをしたが余ってしまったrightの配列内の数字が0で無ければTrue（right_jで確認)
print(result_sort) #=> 並び替えた配列がわかる
return result #最終的な返り値
4 ~ 8 を行っている