Pythonでマージソート

Pocket

マージソートをPythonで書いてみました。

def merge(a, b):
  c = []
  while len(a) > 0 and len(b) > 0:
    if a[0] < b[0]:
      c.append(a.pop(0))
    else:
      c.append(b.pop(0))
  return c + a + b

def mergesort(a):
  num = len(a)
  if num <= 1:
    return a
  else:
    k = num // 2
    x = a[0:k]
    y = a[k:num]
    x = mergesort(x)
    y = mergesort(y)
    return merge(x, y)

上のコードはソート部分とマージ部分を分けていますが一つの関数にまとめると次のとおりです。

def mergesort(a):
  c = []
  x = []
  y = []
  num = len(a)
  if num <= 1:
    return a
  else:
    k = num // 2
    x = a[0:k]
    y = a[k:num]
    x = mergesort(x)
    y = mergesort(y)
    while len(x) > 0 and len(y) > 0:
      if x[0] < y[0]:
        c.append(x.pop(0))
      else:
        c.append(y.pop(0))
    return c + x + y

[ 2021年5月29日 | カテゴリー: Python | タグ: , ]

« | »

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

送信してください。


タグ

カテゴリー

最近の投稿

最近のコメント

固定ページ

アーカイブ

stabucky

写真

メタ情報