目次
Pythonでマージソートのコードを書いてみた
完成コード
def merge(a, b):
c = []
# リスト内が存在するまで繰り返す
while(len(a) > 0) and (len(b) > 0):
# 小さい方をcに追加し、追加した値はリストから削除する
if a[0] < b[0]:
c.append(a[0])
del a[0]
else:
c.append(b[0])
del b[0]
if len(a) > 0:
c.extend(a)
else:
c.extend(b)
return c
def mergeSort(ary):
n = len(ary)
if len(ary) == 1:
return ary
mid = int(round(n/2))
left_ary = ary[:mid]
right_ary = ary[mid:]
# ここから再帰処理
l = mergeSort(left_ary)
r = mergeSort(right_ary)
return merge(l, r)
# 要素の文字列をstr型→bytes型に変換する
encodeNames = []
names = ["サイトウ", "ババ", "タカハシ", "オッペンハイマー", "シマダ", "カトウ", "アイカワ"]
for name in names:
encodeNames.append(name.encode("UTF-8"))
# ソートされたbytes型の配列をstr型に変換して表示する
sortedNames = []
for name in mergeSort(encodeNames):
sortedNames.append(name.decode("UTF-8"))
print(sortedNames)
完成コードの解説をします
1〜18行目が要素を比較して、配列にしていく関数(マージという)です。
20〜34行目で、分割しています。(再帰的な関数になっています)
再帰関数とは?
再帰関数とは、関数内で自分自身を呼び出す処理をしていることをさします。
ここでは、mergeSortという関数の中で、mergeSortという関数を再度呼び出しています。
実行結果
>>> [2, 3, 4, 5, 8, 9, 10, 12, 23, 30]
Pythonの文法を習得するのにおすすめの講座
最後にPythonの文法を習得するのにおすすめの講座を紹介します。
以下の講座は、日本人ですが、アメリカのシリコンバレーで現役エンジニアをやっている方の講座です。
僕も受けていますが、本当に基礎から応用までを網羅しており、最後の方はPythonicな書き方など、実際の現場で求められるような知識もバンバン出てくるので、とてもおすすめです!