こんばんは。
マージソートを勉強してみました。
残念なことに、参考にしている教科書の記述がどうしても
肌に合わなかったので、色々と有識者のコードを拝見しました(*´з`)。
理解がまとまったので、微力ながら、記事として残します。
取り急ぎ、マージソートのイメージを作りました。
こちらです。
最初にやることは、図にある通り、死ぬほど分割することです。
分割した後にそれぞれを比較し、
新しい配列に小さい順から入れなおしてくアルゴリズムのようです。
まず分割の考え方ですが,(右端 + 左端)//2 で行います。
この右端、左端の値を上手く与えて再帰処理することで、配列長を細かく分割することが出来ます。
あと、上図では割愛していますが、[7,0] は実は [7],[0] まで分けて、
比較して小さい方から順に新たな配列に代入するアプローチで [0,7] に再編しています。
そのお隣に居る [1] は比較対象がないので、そのまま保持です。
同様に [5,4] も [5],[4] まで分割し、
比較して小さい方から順に新たな配列に代入しているので [4,5] となります。
断片的で申し訳ありませんが、[7,0]の配列を [0,7] に変える挙動をコードに落とします。
def marge_sort(a):
cen = len(a)//2 #中央値を決定
sleft = a[:cen] #左側の範囲を指定 <= a[0]生成
sright= a[cen:] #右側の範囲を指定 <= a[1]生成
return marge_list(sleft,sright)#a[0]とa[1]を合体し、並べ替え
def marge_list(left,right):
sorted_list = []#カラのリスト
#a[0],a[1]の比較と昇順に並び替え
while len(left) > 0 and len(right) > 0:
if left[0] > right[0]:
sorted_list.append(right[0])#リストをアップデート
right.pop(0)#popで0番目のデータを削除し、right 内のデータを左詰め
else:
sorted_list.append(left[0])#リストをアップデート
left.pop(0)#popで0番目のデータを削除し、left 内のデータを左詰め
#前述の while 文で代入しきれなかった余りを最後に追加
if len(left) > 0:
sorted_list.extend(left)
else:
sorted_list.extend(right)
#return で、しっかり処理結果を返さないとダメです!!
return sorted_list
if __name__ == "__main__":
a = [7,0]
print(f"before sorted is {a}")
print(f"after sorted is {marge_sort(a)}")
before sorted is [7, 0]
after sorted is [0, 7]
前述の再帰処理の伏線をビンビン感じる、ずいぶん遠回りな記述ですね(笑)
では、配列長 2 以上でも対応できるように変えていきます。
def marge_sort(a):
if len(a) <= 1: # 配列長が 1 以下なら return a で戻る
return a
cen = len(a)//2
sleft = a[:cen]
sright= a[cen:]
left =marge_sort(sleft) # 配列長が 1 になるまで繰り返し
right =marge_sort(sright)# 配列長が 1 になるまで繰り返し
return marge_list(left,right)
def marge_list(left,right):
sorted_list = []
while len(left) > 0 and len(right) > 0:
if left[0] > right[0]:
sorted_list.append(right[0])
right.pop(0)
else:
sorted_list.append(left[0])
left.pop(0)
if len(left) > 0:
sorted_list.extend(left)
else:
sorted_list.extend(right)
return sorted_list
if __name__ == "__main__":
a = [7,0,1,5,4,6,3,8,2] # <= 適当な値を入れて試してみてください!
print(f"before sorted is {a}")
print(f"after sorted is {marge_sort(a)}")
はい、配列長 1 であれば return する記述と
再帰処理を冒頭に追加しただけです(笑)。
でも、この記述はとても重要で、1 まで分割し、
更に 1 以下になったらreturnすることで
再帰処理が上手く行くように調整しています。
冒頭に記述している通り、各要素を配列長1まで
分割して並び替えるイメージがないとマージソートは理解が難しいです。
あとは、pop, append は非常に便利な記述で、
別記事で勉強したスタック、キューを考えるうえでも非常に重要なモノでした。
興味のある方は過去の記事で
まとめているので御覧ください。
それでは('◇')ゞ
その後
2020/11/07 自分の記事を読み返してみましたが、
残念ながら、この内容だけでマージソートをマスターするには難しいかもしれません。
改めて考察したので、メモいたします。
まずは配列長2 で考えてみる。
# a = [8,9] とする
def marge_sort(a):
Cptr = len(a)//2 # Cptr = 1
Ldata = a[:Cptr] # Ldata = a[:1] = a[0]
Rdata = a[Cptr:] # Rdata = a[1:] = a[1]
#|<= ここから-------------------------------------------------
buff = []
if Ldata < Rdata: #a[0] < a[1] なら
buff.append(Ldata[0]) #buff に Ldata[0](=a[0]) を代入
Ldata.pop(0) #Ldata を空にする
else: #a[0] > a[1] なら
buff.append(Rdata[0]) #buff に Rdata[0](=a[1]) を代入
Rdata.pop(0) #Rdata を空にする
#Rdata/ Ldata で小さいデータが入っている方が
#先に空になる。残った方を buff に入れてあげれば
#並び替えが出来たことになります。
# まだ残っているのは Rdata ? L data?
if len(Rdata)>0:
buff.append(Rdata[0])
else:
buff.append(Ldata[0])
#--------------------------ここまでで 2つの要素を並び替え=>|
return buff
if __name__ == "__main__":
a = [9,7]
print(marge_sort(a))
これでベースが出来ました。
配列長 2 の時は、配列 1 , 1 を比較して
並び替えてました。
では配列長が 4 になった時はどうしましょう。
雑な絵で申し訳ないです。
配列4 は left : 2 , right : 2 と言うように 2 に分割します。
その後は再帰処理で left 2 で後で述べる def sort に投げて並び替えます。
def sort は前述している TwoSort.py の|<== ここから -- ここまで==>| で
定義している内容を流用します。
left 配列長 2, right 配列長 2 をそれぞれ並び替えが出来たとしても、
その後、配列長 2 の left , right を def sort に投げて並び替えるので、
def sort を配列長 2 以上にも対応させる必要があります。
再帰処理を追加し、前述の配列長についても対応させた場合、
以下のようになります。
def marge_sort(a):
if len(a) <= 1:
return a
Cptr = len(a)//2
Ldata = a[:Cptr]
Rdata = a[Cptr:]
LSdata = marge_sort(Ldata)
RSdata = marge_sort(Rdata)
return sort(LSdata,RSdata)
def sort(LSdata,RSdata):
buff = []
while len(RSdata) > 0 and len(LSdata)>0:
if LSdata[0] < RSdata[0]:
buff.append(LSdata[0])
LSdata.pop(0)
else:
buff.append(RSdata[0])
RSdata.pop(0)
#片方の要素だけ集中してLeft[9,7] Right[] となった場合
#残された要素がカラになるまで buff に追加する必要があります
while len(RSdata) > 0 or len(LSdata)>0:
if len(RSdata)>0:
buff.append(RSdata[0])
RSdata.pop(0)
elif len(LSdata)>0:
buff.append(LSdata[0])
LSdata.pop(0)
return buff
if __name__ == "__main__":
a = [9,7,1,4]
print(marge_sort(a))
記事を投稿した当初は extend を使っていますが、
この重要性を分かっていなかったと思います(笑)。
ゼロから組んだ今なら、その有難みが分かる~~