Pythonでクイックソート完全解説

クイックソートの概要

クイックソートは、高速な比較ベースのソートアルゴリズムで、データをピボット（基準値）を中心に分割し、再帰的にソートを行います。平均計算時間は O(n log n) で、最悪の場合は O(n^2) ですが、実際には非常に高速で動作することが多いです。

クイックソートの手順

1. ピボットを選択する（例：配列の中央値）。
2. 左側からピボットより大きい要素を探す。
3. 右側からピボットより小さい要素を探す。
4. 2 と 3 で見つかった要素を交換する。
5. 2 から 4 を繰り返し、左側にはピボットより小さい要素、右側にはピボットより大きい要素が集まる。
6. 再帰的に左側の部分配列と右側の部分配列に対して 1 から 5 を繰り返す。

図解

言葉だけでは分かりにくいと思うので、クイックソートのアルゴリズムを実際の値を用いて図解して説明します。以下の整数配列を例に取ります。

配列: [3, 7, 8, 5, 2, 1, 9, 5, 4]

1. ピボット選択：配列の中央値をピボットとして選びます。

ピボット: 5 (中央値)
配列: [3, 7, 8, 5, 2, 1, 9, 5, 4]

2. 分割：左側からピボットより大きい要素（7）、右側からピボットより小さい要素（4）を探し、交換します。

交換: 7 と 4
配列: [3, 4, 8, 5, 2, 1, 9, 5, 7]

3. 分割：続けて、左側からピボットより大きい要素（8）、右側からピボットより小さい要素（2）を探し、交換します。

交換: 8 と 2
配列: [3, 4, 2, 5, 8, 1, 9, 5, 7]

4. 分割：続けて、左側からピボットより大きい要素（8）、右側からピボットより小さい要素（1）を探し、交換します。

交換: 8 と 1
配列: [3, 4, 2, 5, 1, 8, 9, 5, 7]

この時点で、ピボット（5）を中心に左側には小さい要素が、右側には大きい要素が集まりました。

5. 再帰：ピボットを中心に左側の部分配列（[3, 4, 2, 1]）と右側の部分配列（[8, 9, 5, 7]）を再帰的にソートします。

左側の部分配列に対して、同様の手順を繰り返します。

6. 結果：全ての部分配列がソートされたら、結果を得ます。

結果: [1, 2, 3, 4, 5, 5, 7, 8, 9]

この図解を参考にして、クイックソートのアルゴリズムを理解してみてください。ピボット選択、分割、再帰のプロセスを繰り返すことで、配列全体がソートされます。

サンプルコードの解説

以下は、クイックソートを実装したサンプルコードです。

def quick_sort(data, left, right):
    i = left  # left_index
    j = right  # right_index
    pivot = (left + right) // 2  # 軸

    # ソート対象のインデックスを探索
    while True:
        while data[i] < data[pivot]:
            i = i + 1
        while data[j] > data[pivot]:
            j = j - 1
        # 無限ループ終了条件
        if i >= j:
            break
        # 交換
        tmp = data[i]
        data[i] = data[j]
        data[j] = tmp
        # 範囲を一つ狭める
        i = i + 1
        j = j - 1

    # 再帰処理
    if left < i - 1:
        quick_sort(data, left, i - 1)
    if right > j + 1:
        quick_sort(data, j + 1, right)

このコードでは、quick_sort 関数に配列 data、左端インデックス left、右端インデックス right を渡してクイックソートを実行します。

1. i と j が、それぞれ左端インデックスと右端インデックスに初期化されます。
2. ピボットは、配列の中央値に設定されます。
3. i がピボットより大きい要素を、j がピボットより小さい要素を探すためのループが始まります。
4. i がピボットより大きい要素を見つけるまで右に移動し、j がピボットより小さい要素を見つけるまで左に移動します。
5. インデックス i が j 以上になるまで、i の位置にある要素と j の位置にある要素を交換します。この操作により、左側にはピボットより小さい要素が、右側にはピボットより大きい要素が集まります。交換後、i は右に、j は左に移動します。
6. 上記のループが終了したら、i と j の間にある部分配列は、ピボットを中心に分割されています。再帰的に左側の部分配列（left から i - 1）と右側の部分配列（j + 1 から right）をソートします。

このプロセスを繰り返すことで、最終的に配列全体がソートされます。

まとめ

クイックソートは、ピボットを中心に配列を分割し、再帰的に部分配列をソートすることで高速なソートを実現するアルゴリズムです。実際の開発では、標準ライブラリのソート関数を使用することが一般的ですが、アルゴリズムの理解を目的としてクイックソートを実装しました。