Pythonあれこれ（Vol.76掲載）

著者：飯尾 淳

本連載では「Pythonを昔から使っているものの、それほど使いこなしてはいない」という筆者が、いろいろな日常業務をPythonで処理することで、立派な「蛇使い」に育つことを目指します。その過程を温かく見守ってください。皆さんと共に勉強していきましょう。第6回は、やや趣向を変えてアルゴリズムを解説します。前半では関数の再帰的定義とその効率化、後半ではソーティングアルゴリズムについて紹介します。

シェルスクリプトマガジン Vol.76は以下のリンク先でご購入できます。

図1　再帰を使わずに階乗を求める関数を定義した例

def factorial(n):
  retvar = 1
  for i in range(n):
    retvar = retvar * i
  return retvar

図4　メモ化アルゴリズムを使って効率化したfib() 関数の定義例

memo = [0] * 100
memo[0] = memo[1] = 1
def fib(n):
  if memo[n-1] == 0: memo[n-1] = fib(n-1)
  if memo[n-2] == 0: memo[n-2] = fib(n-2)
  if memo[n] == 0: memo[n] = memo[n-1] + memo[n-2]
  return memo[n]

図7　バブルソートを実施する関数の実装例

def bubble_sort(x):
  y = x[:]
  for i in range(len(y)-1):
    for j in range(len(y)-1,i,-1):
      if y[j-1] > y[j]:
        tmp = y[j-1]; y[j-1] = y[j]; y[j] = tmp
    print(y)
  return y

図9　マージソートを実施する関数の実装例

def merge_sort(x):
  retary = []
  if len(x) <= 1:
    retary.extend(x)
  else:
    m = len(x) // 2
    first = merge_sort(x[:m])
    second = merge_sort(x[m:])
    while len(first) > 0 and len(second) > 0:
      retary.append(first.pop(0) \
        if first[0] < second[0] else second.pop(0))
    retary.extend(first if len(first) > 0 else second)
  return retary

図11　ヒープソートを実施する関数の実装例

from heapq import heappush, heappop
　
def heap_sort(x):
  retary = []
  heap = []
  for i in x: heappush(heap, i)
  while len(heap) > 0: retary.append(heappop(heap))
  return retary