Pythonでクイックソートを実装する方法｜初心者向けにサンプルコードを徹底解説

この記事では、クイックソート（QuickSort）のアルゴリズムを使って配列を並べ替えるPythonプログラムの実装方法を、初心者にもわかりやすく解説します。

問題の定義

問題： 与えられた配列を、クイックソートの考え方を利用して昇順にソートすることです。

クイックソートは「分割統治法」と呼ばれる手法に基づく高速なソートアルゴリズムです。まず配列を基準値（ピボット）を境目に2つの部分に分割し、それぞれの部分配列を再帰的にソートしていくことで、最終的に全体が整列された配列を得られます。

クイックソートの仕組み

処理の流れは以下のとおりです。

1. 配列からピボット（基準となる要素）を選びます。ここでは末尾の要素をピボットとしています。
2. ピボットより小さい要素を左側へ、大きい要素を右側へ移動させます（パーティション処理）。
3. ピボットの位置が確定したら、その左右の部分配列に対して同じ操作を再帰的に繰り返します。
4. 部分配列のサイズが1以下になれば、その時点で整列済みとみなし処理を終了します。

Pythonでの実装例

それでは、実際のコードを見ていきましょう。

# パーティション関数（配列を分割する）
def partition(arr, low, high):
    i = (low - 1)
    pivot = arr[high]  # ピボットとして末尾の要素を選択
    for j in range(low, high):
        # 現在の要素がピボット以下の場合
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)

# クイックソート本体（再帰的にソートする）
def quickSort(arr, low, high):
    if low < high:
        # パーティションの基準位置を取得
        pi = partition(arr, low, high)
        # 左右の部分配列をそれぞれソート
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

# メイン処理
arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
quickSort(arr, 0, n - 1)
print("Sorted array is:")
for i in range(n):
    print(arr[i], end=" ")

実行結果

Sorted array is
2 3 4 5 5 6 7 8

コードのポイント解説

partition 関数では、変数 i が「ピボットより小さい要素群の境界」を表しています。ループの中で arr[j] がピボット以下であれば i を進めて要素を交換することで、小さい要素が徐々に左側へ集まっていきます。ループ終了後、ピボットを正しい位置（i+1）に移動させ、そのインデックスを返します。

quickSort 関数は、返されたインデックス pi を基準に、左側（low〜pi-1）と右側（pi+1〜high）の部分配列に対して自分自身を呼び出す再帰構造になっています。これにより、すべての要素が確定するまで分割と整列が繰り返されます。

なお、このプログラムで使われている変数はすべてローカルスコープ内で宣言されており、各再帰呼び出しの中で独立して管理されます。

計算量について

クイックソートの平均計算量は O(n log n) と非常に効率的ですが、最悪の場合（すでにソート済みの配列などで常に偏った分割が起こるケース）には O(n²) まで悪化する可能性があります。ピボットの選び方を工夫することで、このリスクを軽減できます。

まとめ

この記事では、Pythonを使ってクイックソートを実装する方法を学びました。パーティション処理と再帰呼び出しという2つの重要な概念を理解すれば、クイックソートのロジックはシンプルに記述できます。ぜひ自分でもコードを動かしながら、動作の流れを確認してみてください。