見出し画像

分割統治を理解して、クイックソートをPythonでサクッと実装する。

es

久々の投稿。

クイックソートは、配列やリストなどのデータ構造を効率的に整列するために使用されます。このアルゴリズムは、まずデータの構造の中からランダムな要素（これを「ピボット」と呼びます）を選びます。次に、ピボットを基準にデータの構造を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




この記事が気に入ったらサポートをしてみませんか？