Pythonを使ったクイックソート

クイック ソートは、時間計算量が O(nlogn) の一般的に使用される並べ替えアルゴリズムです。実際のアプリケーションでは、通常、クイック ソートは他のソート アルゴリズムよりもはるかに高速です。 Python には多くの組み込み並べ替え関数が用意されていますが、それでもクイックソートを理解して実装することが重要です。この記事では、Python を使用してクイック ソート アルゴリズムを実装します。

クイック ソートの動作原理は、ピボット値 (ピボット) を選択し、リスト内のピボット値より小さいすべての要素をサブリストに配置し、ピボットより大きいすべての要素を配置することです。別のサブリストリストの値。 2 つのサブリストは再帰的にすばやく並べ替えられます。最終的には、すべてのサブリストが再帰的に並べ替えられ、単一の並べ替えられたリストにマージされます。

以下は、Python でクイック ソートを実装するコードです:

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

上記のコードでは、最初にリストの長さをチェックします。リストの長さが 2 未満の場合は、元のリストを返します。それ以外の場合は、リストの最初の要素をピボット値として選択します。次に、リスト内包表記を使用して、ピボット値以下の要素を 1 つのリストに入れ、ピボット値より大きい要素を別のリストに入れます。次に、小さいリストと大きいリストを再帰的に並べ替え、並べ替えたリストを連結し、連結されたリストの中央にピボット値を配置します。

このアルゴリズムでは、適切なベンチマーク数値を選択する必要があります。選択したピボット番号がリスト内の最大 (または最小) 値である場合、再帰的に並べ替えられたサブリストのサイズは 1 だけ減少します。この場合、クイックソート アルゴリズムの時間計算量は O(n2) に低下する可能性があります。この状況を回避するには、基本値をランダムに選択する方法を使用できます。この方法では、基本値がリスト内の最大 (または最小) 値ではない場合に、再帰的に並べ替えられたサブリストの平均サイズが保証されます。

以下は、ベンチマーク値をランダムに選択するための Python コードです:

import random

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot_index = random.randint(0, len(arr) - 1)
        pivot = arr[pivot_index]
        less = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i <= pivot]
        greater = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

上記のコードでは、まず、random.randint() 関数を使用してベンチマーク値をランダムに選択します。次に、ベースライン値以下の要素を 1 つのリストに入れ、ベースライン値より大きい要素を別のリストに入れます。これは前の実装と同様です。

要約すると、Python を介してクイック ソート アルゴリズムを実装し、再帰的にソートされたサブリストのサイズの不均衡を避けるためにベンチマーク値をランダムに選択する方法を使用しました。このアルゴリズムは分割統治の考え方に基づいており、平均的な状況下で O(nlogn) の時間計算量でリストを迅速に並べ替えることができます。

以上がPythonを使ったクイックソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。