分割統治を理解して、クイックソートをPythonでサクッと実装する。
久々の投稿。
クイックソートは、配列やリストなどのデータ構造を効率的に整列するために使用されます。このアルゴリズムは、まずデータの構造の中からランダムな要素（これを「ピボット」と呼びます）を選びます。次に、ピボットを基準にデータの構造を2つのグループに分けます。1つのグループには、ピボットよりも小さい値が含まれます。もう1つのグループには、ピボットよりも大きい値が含まれます。最後に、このアルゴリズムは、この2つのグループを再びクイックソートで整列します。これを繰り返すことで、最終的にデータの構造が昇順に整列されるようになります。
ポイントは終了条件と再帰の部分。
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test the quicksort function
print(quicksort([3,6,8,10,1,2,1])) # [1, 1, 2, 3, 6, 8, 10]クイックソートは、データの構造が大きな場合に非常に効率的です。このアルゴリズムは、平均的にO(n log n)の時間でデータを整列することができます。これは、他のアルゴリズムよりも高速であるため、大規模なデータセットを扱う場合に非常に有用です。
分割統治
よくわからない人は、まず分割統治を理解しましょう。
クイックソートだと以下のコードが分割統治です。
return quicksort(left) + middle + quicksort(right)分割統治法とは、大きな問題を小さな問題に分割して、それぞれを独立して解くことで、問題を解決するアルゴリズムのことを指します。このアルゴリズムでは、まず元の問題を複数の小さな問題に分割し、それぞれを個別に解きます。最後に、これらの小さな問題の解を組み合わせて、元の問題の解を求めます。
分割統治法は、問題が複雑であっても、それを小さな問題に分割することで、解決することができるため、非常に有用なアルゴリズムです。また、分割統治法は再帰的に実装することができるため、コードを簡潔に書くことができます。
以下で、Pythonで分割統治法を用いて、リスト内の最大値を求めるシンプルなプログラムを示します。
def find_max(numbers):
# リストが空の場合は、Noneを返す
if not numbers:
return None
# リスト内の要素が1つだけの場合は、その値を返す
if len(numbers) == 1:
return numbers[0]
# リストを半分に分割する
mid = len(numbers) // 2
left = numbers[:mid]
right = numbers[mid:]
# 分割された2つのリストから、それぞれ最大値を求める
max_left = find_max(left)
max_right = find_max(right)
# 左側のリストと右側のリストから、最大値を求める
return max(max_left, max_right)
find_max([5, 10, 15, 20, 25])
25