Python

マージソートのコードを書いてみた

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な書き方など、実際の現場で求められるような知識もバンバン出てくるので、とてもおすすめです!

Python 3 入門 + 応用 +アメリカのシリコンバレー流コードスタイルを学ぶオンライン講座

COMMENT

メールアドレスが公開されることはありません。