🍣

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

2023/04/17に公開

クイックソートの概要

クイックソートは、高速な比較ベースのソートアルゴリズムで、データをピボット(基準値)を中心に分割し、再帰的にソートを行います。平均計算時間は 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]
  1. 分割:左側からピボットより大きい要素(7)、右側からピボットより小さい要素(4)を探し、交換します。
交換: 7 と 4
配列: [3, 4, 8, 5, 2, 1, 9, 5, 7]
  1. 分割:続けて、左側からピボットより大きい要素(8)、右側からピボットより小さい要素(2)を探し、交換します。
交換: 8 と 2
配列: [3, 4, 2, 5, 8, 1, 9, 5, 7]
  1. 分割:続けて、左側からピボットより大きい要素(8)、右側からピボットより小さい要素(1)を探し、交換します。
交換: 8 と 1
配列: [3, 4, 2, 5, 1, 8, 9, 5, 7]

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

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

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

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

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

まとめ

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

Discussion