【解説】 クイックソート(Quick Sort)
クイックソート（Quick Sort）は、1960年にアントニー・ホーアが考案した、非常に高速で効率的な並べ替え（ソート）アルゴリズムです。多くのプログラミング言語の標準ライブラリでも採用されています。
1. 基本的な考え方
クイックソートは**分割統治法（Divide and Conquer）**という戦略を利用します。大きな問題を小さく分けてから解決していく手法です。
手順の概要
-
軸（ピボット / Pivot）の選択: データの中から基準となる値を1つ選びます。
-
分割（パーティション）: ピボットより「小さい値」のグループと「大きい値」のグループにデータを分けます。
-
再帰: 分けられた各グループに対して、再び手順1〜2を繰り返します。データの数が1つ（または0）になれば完了です。
2. アルゴリズムの仕組み（具体例）
例えば、[5, 3, 8, 4, 9, 1, 6, 2, 7] という配列を昇順に並べ替える場合を考えます。
-
ステップ 1: 最後の要素
7をピボットに選びます。 -
ステップ 2:
7より小さいものを左へ、大きいものを右へ移動させます。-
結果：
[5, 3, 4, 1, 6, 2]（7より小） +[7]+[8, 9]（7より大）
-
-
ステップ 3: 左右のグループに対して同じ操作を繰り返します。
-
左側
[5, 3, 4, 1, 6, 2]で新たにピボット（例：2）を選び、分割します。 -
右側
[8, 9]で新たにピボット（例：9）を選び、分割します。
-
-
最終ステップ: すべての要素がバラバラになり、結合されると
[1, 2, 3, 4, 5, 6, 7, 8, 9]になります。
（トレース）
538491627
[534162]7[89]
[1]2[5346]789
12[534]6789
12[3]4[5]6789
123456789
3. クイックソートの特徴
メリット
-
平均実行速度が非常に速い: 平均的な計算量は
です。 -
追加のメモリが少なくて済む: データの入れ替えを元の配列内で行う（インプレース）ことが可能です。
デメリット・注意点
-
最悪の場合の計算量: ピボットの選び方が極端に悪い（既に整列されたデータで端をピボットにするなど）と、
に低下します。 -
不安定なソート: 同じ値を持つ要素の前後関係が入れ替わることがあります（安定ソートではない）。
# クイックソート
def quick_sort(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 quick_sort(left) + middle + quick_sort(right)
# 使用例
data = [3, 6, 8, 10, 1, 2, 1]
print(f"ソート後: {quick_sort(data)}")