Python で 2つの並べ替えられたリストをマージする

1. Python で 2つの並べ替えられたリストをマージする
2. Python で 2つのソートされたリストをマージする単純なアプローチ
3. Python で heapq.merge() メソッドを使用して 2つの並べ替えられたリストをマージする
4. Python で sorted() 関数を使用して 2つの並べ替えられたリストをマージする
5. まとめ

ソートされたリストは、昇順または降順に並べられたリストであり、これらのソートされたリストをマージするとは、ソートされたままの方法で 2つのリストの両方を結合することを指します。

Python には、2つのソートされたリストをマージできるさまざまな方法があります。 Python には、このタスクを実行するための組み込み関数がありますが、これらの組み込み関数を設計するために使用される単純なアプローチについても説明します。

Python で 2つの並べ替えられたリストをマージする

この記事では、問題の説明が与えられ、その解決策を設計するよう求められます。 問題は、個別にソートされた 2つのリストがあることですが、マージ後もソートされた状態を維持するには、それらをマージする必要があります。

例でこれを理解しましょう。

list1 = [2, 5, 7, 8, 9]
list2 = [0, 1, 3, 4, 6]

出力：

Sorted List: [0,1,2,3,4,5,6,7,8,9]

出力のソートされたリストは、リスト list1 と list2 の要素で構成されています。 マージされた後、結合されたリストがまだソートされるように配置されます。

この問題は、マージソートで使用される merge 関数の設計と同じです。 したがって、これらの質問を解決する際に、この種の問題に遭遇することがよくあります。

したがって、それにどのようにアプローチするかについての基本的な考え方が必要です。 さて、この問題をどのように解決するかを理解しましょう。

Python で 2つのソートされたリストをマージする単純なアプローチ

ここで説明するソリューションは、Python で 2つの並べ替えられたリストをマージする単純なアプローチです。 このアプローチでは、両方のリストを同時にトラバースし、現在の位置にある 2つの要素の間で小さい方の要素を確認します。

小さい方の要素が回答に追加されます。 ただし、2つのリストのいずれかが完全にトラバースされると、マージされた要素の後に、もう一方のリストが結果に追加されます。

理解を深めるためにコードを見てみましょう。

firstList = [2, 7, 8, 9]
secondList = [0, 1, 4, 6]
result = []
i, j = 0, 0

while i < len(firstList) and j < len(secondList):
    if firstList[i] < secondList[j]:
        result.append(firstList[i])
        i = i + 1
    else:
        result.append(secondList[j])
        j = j + 1

result = result + firstList[i:] + secondList[j:]
print("Sorted List: " + str(result))

出力：

Sorted List: [0, 1, 2, 4, 6, 7, 8, 9]

上記のコードでは、マージされたリストを格納する空のリスト result を宣言しました。 次に、どちらかまたは両方が使い果たされるまで、両方のリストを繰り返し処理しました。

ループ内で、両方のリストの要素を比較し、小さい方の要素を result 変数に追加します。その後、現在のインデックスを 1 増やします。

いずれかのリストに結果に含まれていない要素がある場合は、Python のスライス演算子を使用して、残りの要素を回答にマージします。

このアプローチでは、リストを 1 回だけ繰り返しました。 したがって、時間の複雑さは O(n1+n2) ですが、上記のアプローチの空間の複雑さも O(n1+n2) であり、n1 と n2 はソートされたサイズを表します。 リスト。

Python で heapq.merge() メソッドを使用して 2つの並べ替えられたリストをマージする

Python の heapq モジュールはヒープ キューを参照します。 ただし、このモジュール Heapq は、主に Python でプライオリティ キューを実装するために使用されます。

heapq モジュールには Python の merge() 関数が含まれています。この関数は、複数の並べ替えられたリストを引数として取り、1つの組み合わせてマージされたリストを返します。

Python で heapq.merge() 関数を使用してマージ操作を実行する方法を見てみましょう。

from heapq import merge

first = [2, 7, 8, 9]
second = [0, 1, 4, 6]

res = list(merge(first, second))

print("Merged Sorted list: ", str(res))

出力：

Merged Sorted list:  [0, 1, 2, 4, 6, 7, 8, 9]

上記のコードでは、merge() 関数で 2つのソート済みリスト first と second を引数として渡し、その後、明示的にリストに変換しています。 その結果、マージされたソート済みリストは、ans 変数に格納されます。

ご覧のとおり、heapq モジュールの merge() 関数を使用して、Python で 2つのソート済みリストをマージできます。

Python で sorted() 関数を使用して 2つの並べ替えられたリストをマージする

Python の sorted() 関数は、パラメーターとして提供されたリストまたはタプルをソートします。 元の順序を変更せずにソートされるリストを常に返します。

この関数を使用して、問題を 1 行で解決できます。 両方のリストを一緒に追加し、sorted() 関数を結果のリストに適用します。

例を挙げて理解してみましょう。

first = [2, 7, 9]
second = [0, 1, 4]

result = sorted(first + second)

print("List after sorting: ", str(result))

出力：

List after sorting:  [0, 1, 2, 4, 7, 9]

上記のプログラムでは、+ 演算子を使用して 2つのリストを一緒に追加しました。 連結演算子 + は、コードに入力された順序で複数のリストを 1つの結合リストに追加するために使用されます。

その後、追加されたリストに sorted() 関数を適用しました。これにより、シーケンスがソートされ、結果が出力されます。

内部的に、2つのリストを 1つのリストに追加しているため、上記の他の 2つのアプローチよりも時間がかかるため、このアプローチには時間がかかる場合があります。

まとめ

この記事では、Python で 2つの並べ替えられたリストをマージできるさまざまなアプローチについて説明します。 そのうちの 2つは Python の組み込みメソッドですが、もう 1つは問題に対する詳細なアプローチです。

sorted() 関数は、追加されたリストを並べ替えるために使用される組み込み関数の 1つですが、もう 1つの heapq.merge() は、Python で 2つの並べ替えられたリストをマージするために使用されるメソッドです。 どちらの関数も、1 行で操作を実行できます。

詳細なアプローチは、リストを反復処理し、現在のインデックスで各要素を比較し、小さい方の要素を答えに追加してから、現在のインデックスを 1 増やします。このループは、リストのいずれかまたは両方が使い果たされるまで実行され、その後、残りの 要素は、Python のスライス演算子によって追加されます。

上記の方法のいずれかを使用して、問題を解決できます。