Pythonで2つの未ソートのリストをマージしてソート済みリストを作成する方法

ここでは、ユーザーが入力した2つのリストが与えられます。各リストの要素はソートされていない状態です。この記事の目的は、これら2つの未ソートのリストを1つにマージし、その後リスト全体を昇順に並べ替えることです。

例

入力: A[] = {100, 50, 150}
      B[] = {200, 30, 20}
出力: マージ後のリスト: {20, 30, 50, 100, 150, 200}

アルゴリズム

ステップ1: まず、ユーザー入力による2つのリストを作成します。
ステップ2: 最終的なマージリストのサイズは「1つ目のリストのサイズ + 2つ目のリストのサイズ」になります。
ステップ3: sort()メソッドを使って、両方のリストをそれぞれソートします。
ステップ4: ソート済みの2つのリストをマージし、3つ目のリストに格納します。
ステップ5: a[]に残った要素(存在する場合)とb[]に残った要素(存在する場合)をマージします。
ステップ6: マージ・ソートされたリストを表示します。

サンプルコード

# 2つの未ソートのリストを
# 昇順にマージするPythonプログラム
# 配列を昇順にマージする関数
def unsortedarray(a, b, res, n, m):
   # a[]とb[]をそれぞれソート
   a.sort()
   b.sort()
   # ソート済みの2つの配列をres[]へマージ
   i, j, k = 0, 0, 0
   while (i < n and j < m):
      if (a[i] <= b[j]):
         res[k] = a[i]
         i += 1
         k += 1
      else:
         res[k] = b[j]
         j += 1
         k += 1
   while (i < n):  # a[]の残りの要素をマージ(存在する場合)
      res[k] = a[i]
      i += 1
      k += 1
   while (j < m):  # b[]の残りの要素をマージ(存在する場合)
      res[k] = b[j]
      j += 1
      k += 1
# ドライバーコード
A = list()
n = int(input('1つ目のリストのサイズを入力してください:'))
print('1つ目のリストの要素を入力してください:')
for i in range(int(n)):
   k = int(input(''))
   A.append(k)
B = list()
m = int(input('2つ目のリストのサイズを入力してください:'))
print('2つ目のリストの要素を入力してください:')
for i in range(int(m)):
   k = int(input(''))
   B.append(k)
# 最終的なマージリスト
res = [0 for i in range(n + m)]
unsortedarray(A, B, res, n, m)
print('ソート済みマージリスト:')
for i in range(n + m):
   print(res[i],)

実行結果

1つ目のリストのサイズを入力してください: 4
1つ目のリストの要素を入力してください:
8
79
56
3
2つ目のリストのサイズを入力してください: 4
2つ目のリストの要素を入力してください:
67
1
9
45
ソート済みマージリスト:
1
3
8
9
45
56
67
79

処理のポイント

このプログラムでは、まずsort()メソッドによって両方のリストを個別に昇順ソートし、その後マージソートと同じ考え方で、先頭同士を比較しながら小さい方から新しいリストへ移していきます。どちらか一方のリストの要素がすべて処理された後も、もう一方のリストに残りがある場合は、それらをそのまま末尾へ追加します。計算量はO((n+m) log(n+m))となり、リストの合計サイズに対して効率的に動作します。

さらに簡単な方法:sorted()を使う

なお、Pythonでは組み込み関数sorted()を活用すれば、手動でのマージ処理を書かなくても、わずか数行で同じ結果を得られます。

A = [100, 50, 150]
B = [200, 30, 20]
merged = sorted(A + B)
print('マージ後のリスト:', merged)
# 出力: マージ後のリスト: [20, 30, 50, 100, 150, 200]

アルゴリズムの学習や面接対策としては前者の実装方法を理解しておくことが重要ですが、実際の開発ではsorted()を使った簡潔な記述が推奨されます。用途に応じて使い分けるとよいでしょう。