Pythonで実装する反復型（非再帰）クイックソートのプログラム

この記事では、次の問題に対する解決策をPythonのコードとともに詳しく解説します。

問題の概要

問題文： 与えられた配列を、クイックソートの考え方を利用して反復的（非再帰的）な手法でソートします。

通常、クイックソートは再帰呼び出しによって実装されることが多いですが、ここでは明示的にスタックを使用することで、再帰なしに同じアルゴリズムを実現します。まず配列をパーティション（分割）し、その各部分を個別にソートしていくことで、最終的に全体がソートされた配列を得ます。

アルゴリズムの流れ

1. ソート対象の範囲（開始インデックス l と終了インデックス h）をスタックにプッシュする。
2. スタックが空になるまで、範囲をポップしてはパーティション関数でピボットを正しい位置に配置する。
3. ピボットの左側・右側に未ソートの要素が残っていれば、その範囲を再度スタックにプッシュする。
4. これを繰り返すことで、再帰を使わずに配列全体をソートする。

実装例

# 反復的な方法
def partition(arr,l,h):
    i = ( l - 1 )
    x = arr[h]
    for j in range(l , h):
        if arr[j] <= x:
            # インクリメント
            i = i+1
            arr[i],arr[j] = arr[j],arr[i]
    arr[i+1],arr[h] = arr[h],arr[i+1]
    return (i+1)
# ソート
def quickSortIterative(arr,l,h):
    # スタックの作成
    size = h - l + 1
    stack = [0] * (size)
    # 初期化
    top = -1
    # 初期値をプッシュ
    top = top + 1
    stack[top] = l
    top = top + 1
    stack[top] = h
    # スタックからポップ
    while top >= 0:
        # ポップ
        h = stack[top]
        top = top - 1
        l = stack[top]
        top = top - 1
        # ピボット要素を正しい位置に設定
        p = partition( arr, l, h )
        # 左側の要素
        if p-1 > l:
            top = top + 1
            stack[top] = l
            top = top + 1
            stack[top] = p - 1
        # 右側の要素
        if p+1 < h:
            top = top + 1
            stack[top] = p + 1
            top = top + 1
            stack[top] = h
# メイン処理
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quickSortIterative(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

上記の例では、初期配列 [2, 5, 3, 8, 6, 5, 4, 7] が正しく昇順にソートされていることが確認できます。

すべての変数はローカルスコープ内で宣言されており、それぞれの参照関係は図のようになっています。パーティション関数は配列の末尾の要素をピボットとして選択し、ピボットより小さい要素を左側に集めることで、ピボットを最終的な正しい位置へ移動させます。

計算量について

この反復型クイックソートの時間計算量は、一般的なクイックソートと同様に平均で O(n log n)、最悪ケース（すでにソート済みの配列など）では O(n²) となります。一方で、再帰呼び出しを行わないため、深い再帰によるコールスタックのオーバーフローを心配する必要がなく、メモリ使用量もスタック配列のサイズ分だけで抑えられるという利点があります。

まとめ

この記事では、Pythonを使って再帰呼び出しに頼らない反復型クイックソートを実装する方法を学びました。スタックを明示的に管理することで、再帰版と同じロジックを安全かつ効率的に実現できる点は、大規模データや再帰深度の制限がある環境で特に有用です。