クイックソート

9.1 クイックソートの定義

クイックソート (Quick Sort) は「分割統治法」を利用する効率的なソートアルゴリズムだよ。ピボットと呼ばれる要素を選ぶことで、配列を2つのサブ配列に分けるんだ。一つはピボットより小さい要素、もう一つは大きい要素で、それぞれのサブ配列に対してこのプロセスを再帰的に適用するんだ。

クイックソートアルゴリズムは、「小さい要素を左に、大きい要素を右に素早く移動させる」問題を解決するために生まれた。例えば、一番小さい要素が一番右にあるとき、どうにかしてそれを最終位置に近づけることができるかな？そうすれば不要な比較を大幅に減らせるね。

動作原理:

1. ピボットの選択:

配列からピボットを選ぶよ。ピボットは最初の要素、最後の要素、真ん中の要素、ランダムな要素などから選べる。時にはランダムな要素3つの平均値を使うこともあるよ。

2. 分割 (partitioning):

ピボットより小さい要素を配列の左側に、ピボットより大きい要素を右側に移動するよ。結果として、ピボットはソート後の配列で最終的な位置に来る。

3. 再帰的適用:

左右のサブ配列に対してピボットを含まないように再帰的にプロセスを適用する。

ステップバイステッププロセス

1. ピボットを選ぶ。
2. ピボットより小さい要素を左に、大きい要素を右に移動する。
3. サブ配列に再帰的にプロセスを適用する。

クイックソートの時間と空間の複雑性

時間の複雑性:

• 最悪の場合: O(n^2) — 毎回最悪のピボットが選ばれると発生する（例えば、配列がすでにソートされている場合）。
• 平均の場合: O(n log n) — ランダムに分布したデータのとき。
• 最良の場合: O(n log n) — 配列が毎回均等に分割される場合。

空間の複雑性:

O(log n) — 末端再帰とピボットの選択がうまくできた場合に必要な再帰呼び出しスタックの保存用だよ。

9.2 クイックソートアルゴリズムの実装

Pythonでの実装:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # 基本ケース: 要素が0または1の配列はすでにソート済み
    
    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)

# 使用例:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("ソート済み配列:", sorted_arr)
# 出力: ソート済み配列: [1, 1, 2, 3, 6, 8, 10]

アルゴリズムの動作例

配列の例: [3, 6, 8, 10, 1, 2, 1]

初回通過:

• ピボット: 8
• 左の要素: [3, 6, 1, 2, 1]
• 中央の要素: [8]
• 右の要素: [10]

左側 [3, 6, 1, 2, 1] の再帰的ソート:

• ピボット: 1
• 左の要素: []
• 中央の要素: [1, 1]
• 右の要素: [3, 6, 2]

右側 [3, 6, 2] の再帰的ソート:

• ピボット: 6
• 左の要素: [3, 2]
• 中央の要素: [6]
• 右の要素: []

左側 [3, 2] の再帰的ソート:

• ピボット: 2
• 左の要素: []
• 中央の要素: [2]
• 右の要素: [3]

マージの結果: 左側に [1, 1, 2, 3, 6]、右側に [10]、中央に [8] が返る。

最終的なソート済み配列: [1, 1, 2, 3, 6, 8, 10]