Pythonで視覚的に理解するクイックソートの実装

はじめに

こんにちは！今回はクイックソート(Quick Sort)をPythonで実装し、その過程を再帰の深さを視覚化することで、処理の流れがわかりやすくなる工夫を加えました。

クイックソートとは？

クイックソートは以下の手順で動作します。
配列の要素を基準値(pivot)に基づいて2つの部分配列に分割し、それぞれの部分配列を再帰的ソートしていきます。

1. 基準値を選択(通常は配列の最初の要素や最大の要素を基準にします)
2. 基準値より小さい値を左側、大きな値を右側に並べる
3. 左右の部分配列を再帰的にソート

実装コード

以下は Python でのクイックソートの実装コードです。
再帰の深さに応じてインデントを付けることで、処理の流れをわかりやすくしています。

def quicksort(arr, left, right, depth=0):
    """ クイックソートを再帰的に実行し、処理の流れを視覚化する """
    indent = "  " * depth  # 再帰の深さをインデントで表現

    if left < right:
        print(f"\n{indent}【クイックソート開始】 部分配列: {arr[left:right+1]}")

        # 手順1: 基準値の選択
        k = arr[left]
        print(f"{indent}手順1: 基準値として {k} を選択")
        print(f"{indent}現在の配列: {arr}")

        # 手順2: 基準値を右端と交換
        arr[left], arr[right] = arr[right], arr[left]
        print(f"{indent}手順2: 基準値を右端と交換")
        print(f"{indent}交換後の配列: {arr}")

        i, j = 0, right - 1

        while True:
            # 手順3: 左から探索
            while i < right and arr[i] <= k:
                i += 1
            if i < right:
                print(f"{indent}手順3: 基準値以上のデータ {arr[i]} を位置 {i} で発見")

            # 手順4: 右から探索
            while j >= left and arr[j] >= k:
                j -= 1
            if j >= left:
                print(f"{indent}手順4: 基準値未満のデータ {arr[j]} を位置 {j} で発見")

            # 手順5: データの交換
            if i < j:
                print(f"{indent}手順5: データ交換 {arr[i]} ⇔ {arr[j]}")
                arr[i], arr[j] = arr[j], arr[i]
                print(f"{indent}交換後の配列: {arr}")
            else:
                print(f"{indent}手順6: 分割完了 (i={i} > j={j})")
                break

        # 手順7: 基準値を最終位置に配置
        print(f"{indent}手順7: D[i]={arr[i]} と D[right]={arr[right]} のデータを交換")
        arr[i], arr[right] = arr[right], arr[i]
        print(f"{indent}配置後の配列: {arr}")

        # 再帰的に左右の部分配列をソート
        print(f"{indent}左側の部分配列をソート: {arr[left:i]}")
        quicksort(arr, left, i - 1, depth + 1)

        print(f"{indent}右側の部分配列をソート: {arr[i+1:right+1]}")
        quicksort(arr, i + 1, right, depth + 1)

実行例

テストデータとして以下の配列をソートします。

D = [74, 47, 91, 94, 15, 13, 72, 31]
print("【初期配列】:", D)
quicksort(D, 1, len(D) - 1)  # 最初の基準値を D[1] = 47 とする
print("\n【ソート完了】最終結果(解答):", D)

実行結果

【初期配列】: [74, 47, 91, 94, 15, 13, 72, 31]

  【クイックソート開始】 部分配列: [47, 91, 94, 15, 13, 72, 31]
  手順1: 基準値として 47 を選択
  現在の配列: [74, 47, 91, 94, 15, 13, 72, 31]
  手順2: 基準値を右端と交換
  交換後の配列: [74, 31, 91, 94, 15, 13, 72, 47]
  ...
  ・
  ・
  ・
【ソート完了】最終結果(解答): [13, 15, 31, 47, 72, 74, 91, 94]

コードの説明

quicksort(arr, left, right, depth=0)

再帰的にクイックソートを行う関数です。再帰の深さを引数depthで管理し、深さに応じたインデントを付けて処理の流れを追跡できるようにしています。

• 手順1~7で分割・基準値配置を行い、左右に部分配列をそれぞれ再帰的にソートします
• 再帰の途中経過をコンソールに出力することで、どの部分配列が現在ソートされているか視覚的にわかります

まとめ

クイックソートは、最悪計算量がO(n^2)である一方で、平均計算量はO(nlogn) という非常に効率的なソートアルゴリズムです。
再帰的な処理の流れがわかりやすくなるように工夫しているので、ぜひ試してみてください。最後まで読んでくださり、ありがとうございました。もし改善点や質問があれば、ぜひコメントしてください！