マージソート
もしマージソートを簡単に学びたいなら、理解を深めるためにこのビデオを見てください。📊✨
マージソートとは？
マージソートは分割統治アルゴリズムで、問題を再帰的にサブ問題に分解します。
入力配列をより小さな配列に分割し、各配列が単一の要素を含むまで続けます。その後、ソートされた配列が2つずつマージされてソートされたサブ配列が生成され、サブ配列をマージしてソートされた配列が得られます。
🌟 やり方を見てみましょう
これは未ソートの配列です。例えば、人それぞれ身長が異なるので、理論を理解しやすくなります。このマージソートを使って要素を昇順に並べる方法を見ていきます。
次に、私たちは元の配列を分割します。最初に、配列の下端インデックスと上端インデックスを取得したいと思います。インデックスは0から始まります。この配列には[8, 5, 13, 7, 2, 1, 4]があり、7つの要素（配列の長さ）があります。インデックスは6です。
下端は0で、上端は6です。中央値を見つけるために、これらを加算し、その合計を2で割り、その結果にフロア関数を適用します。すると、結果は3になります。
(フロア関数は => もし結果が3.5の場合、フロア関数はそれを3に変換します。つまり、結果と等しいかそれ以下の最大の整数を返します。)
さて、インデックス3から配列を分割できます。2つのサブ配列が得られます。
再び、このサブ配列を分割するために同じことを行います。
サブ配列を再帰的に分割し、配列内に単一の要素が残るまで続けます。以下の図のような結果が得られます。
さて、これらのサブ配列をマージする準備をします。まず、マージする配列を取得します。8と5の配列をマージすることにします。次に、8が5より小さいかどうかを確認します。答えは「いいえ」です。もし答えがfalseであれば、2つの要素を入れ替えて正しい順序にします。
入れ替えた後、もう一度5が8より小さいかどうかを確認します。そうすると、それはtrueです。これで2つの配列はソートされました。
これと同じことを再帰的に繰り返し、最終的に元の配列が昇順になる結果を得るまで続けます。
これはPythonで書かれたコードです。これがマージソートを明確に理解するのに役立つことを願っています。
def merge_sort(arr):
if len(arr)>1:
left= arr[:len(arr)//2]
right= arr[len(arr)//2:]
#recursion
merge_sort(left)
merge_sort(right)
#merge
l=0
r=0
m=0
while l < len(left) and r<len(right):
if left[l] < right[r]:
arr[m]= left[l]
l+=1
else:
arr[m] = right[r]
r+=1
m+=1
while l < len(left):
arr[m] = left[l]
l+=1
m+=1
while r<len(right):
arr[m]= right[r]
r+=1
m+=1
array=[8,5, 13, 7, 2, 1, 4]
print(" Before sort : ")
print(array)
merge_sort(array)
print("After merge sort :")
print(array)
