Python クイックソート実装：基本とコード例

クイックソートは一般的なソートアルゴリズムであり、基本的なアイデアは、基準値を選択し、配列を2つの部分に分けることである。一方は基準値より小さく、他方は基準値より大きくなります。そして、それぞれの部分の配列を再帰的にソートします。

Pythonでクイックソートを実装するコードの例を以下に示します:

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

# 测试示例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)

この例では、クイックソートアルゴリズムを実装するためにquick_sort関数を定義します。まず、配列の長さが1以下かどうかを判断し、そうであれば配列を直接返します。そうでなければ、配列の最初の要素を基準値として選択し、リスト内包表記を使用して基準値以下および基準値より大きい2つのサブ配列lessとgreaterを取得し、最後にそれぞれのサブ配列に再帰的にソートを行い、結果をマージして返します。

Pythonのインタプリタに上記のコードをコピー＆ペーストして実行し、クイックソートアルゴリズムの効果をテストできます。