Python でのマージソート
マージソートは、特定のデータ構造の要素をソートするために使用される一般的なソートアルゴリズムです。このチュートリアルでは、マージソートアルゴリズムとそれを Python で実装する方法について説明します。
マージソートは分割統治アプローチの代表的な例であり、大規模なデータセットのソートに使用されます。アルゴリズムは、指定されたデータ構造を 2つの部分に分割することから始まり、次に両方の半分で同じプロセスを繰り返します。最後に、半分を組み合わせて、ソートされた値を効率的に取得します。したがって、これを分割統治アプローチの代表的な例と呼びます。
このアルゴリズムの最良の部分は、3つの可能なすべてのケース（平均ケース、最良ケース、および最悪ケース）で O(nlogn) の一貫した時間計算量を持っていることです。この事実により、一般的に効率的であると考えられており、大規模なデータセットに適しています。
ここでは、Python プログラミング言語を使用してマージソートアルゴリズムを実装する方法を説明します。
Python で再帰を使用してマージソートを実装する
マージソートは、再帰関数を使用して Python で簡単に実装されます。
次のコードは、再帰を使用して Python でマージソートを実装します。
def m(left, right):
if not len(left) or not len(right):
return left or right
result = []
i, j = 0, 0
while len(result) < len(left) + len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i == len(left) or j == len(right):
result.extend(left[i:] or right[j:])
break
return result
def msort(list):
if len(list) < 2:
return list
middle = int(len(list) / 2)
left = msort(list[:middle])
right = msort(list[middle:])
return m(left, right)
lst = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(lst)
print("\n")
print("Sorted List:")
print(msort(lst))
上記のコードは、次の出力を提供します。
Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]
コードの説明：
- 指定されたリストは、2つの隣接する値が取得されない限り、すべての再帰呼び出しで
左と右の 2つに分けられます。 m()関数が作成され、最初のステップで最初に分割された 2つの半分をマージするために使用されます。msort()関数は、プログラム内の指定されたリストの分割と並べ替えの部分のほとんどを実行します。
Python で反復マージソートを使用する
反復マージソートアルゴリズムは、前者がボトムアップアプローチを使用し、後者が上から下へのアプローチを使用するため、一般的な再帰的方法とは少し異なります。ただし、時間計算量と最終的な答えは、どちらの方法でもまったく同じです。
さらに、再帰的マージソート方式では明示的な補助スタックを使用しますが、反復マージソートアルゴリズムの実装ではその必要はありません。
次のコードは、反復マージソートアルゴリズムを使用して、Python でマージソートを実装します。
def msort(a):
width = 1
n = len(a)
while width < n:
l = 0
while l < n:
r = min(l + (width * 2 - 1), n - 1)
m = (l + r) // 2
if width > n // 2:
m = r - (n % width)
mer(a, l, m, r)
l += width * 2
width *= 2
return a
def mer(a, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * n1
R = [0] * n2
for i in range(0, n1):
L[i] = a[l + i]
for i in range(0, n2):
R[i] = a[m + i + 1]
i, j, k = 0, 0, l
while i < n1 and j < n2:
if L[i] > R[j]:
a[k] = R[j]
j += 1
else:
a[k] = L[i]
i += 1
k += 1
while i < n1:
a[k] = L[i]
i += 1
k += 1
while j < n2:
a[k] = R[j]
j += 1
k += 1
a = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(a)
msort(a)
print("Sorted List:")
print(a)
上記のコードは、次の出力を提供します。
Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]
マージソートのデメリット
マージソートは非常に人気があり、非常に効率的であると考えられていますが、さまざまな場合にいくつかの欠点があります。これについては、以下で説明します。
- データ構造のより小さなセットを処理する場合、他の利用可能なソートアルゴリズムよりも比較的遅くなる可能性があります。
- このアルゴリズムを実装するには、追加のメモリスペースが必要です。
- アルゴリズムは、指定されたデータ構造がすでに並べ替えられている場合でも、常にプロセス全体を実行します。
Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.
LinkedIn