Pythonでサイクルソートを実装する方法

この記事では、次の問題に対する解決策をわかりやすく解説していきます。

問題文

配列が与えられたとき、サイクルソート（Cycle Sort）の考え方を用いてその配列をソートします。

サイクルソートはインプレース（in-place）アルゴリズムの一種で、要素の入れ替え（スワップ）を「サイクル（循環）」を形成する形で行うのが大きな特徴です。理論上の書き込み回数が最小となるよう設計されているため、メモリへの書き込みコストが高い環境で特に有用とされるアルゴリズムです。

それでは、以下の実装例で具体的な解決策を見ていきましょう。

実装例

def cycleSort(array):
    writes = 0
    # 回転させるサイクル
    for cycleStart in range(0, len(array) - 1):
        item = array[cycleStart]
        # 要素を配置する位置
        pos = cycleStart
        for i in range(cycleStart + 1, len(array)):
            if array[i] < item:
                pos += 1
        # すでに正しい位置にある場合はサイクルではないためスキップ
        if pos == cycleStart:
            continue
        # それ以外の場合、要素を配置する
        while item == array[pos]:
            pos += 1
        array[pos], item = item, array[pos]
        writes += 1
        # サイクルが閉じるまで回転を継続
        while pos != cycleStart:
            # 次の要素を配置する位置を探す
            pos = cycleStart
            for i in range(cycleStart + 1, len(array)):
                if array[i] < item:
                    pos += 1
            # 要素を配置する
            while item == array[pos]:
                pos += 1
            array[pos], item = item, array[pos]
            writes += 1
    return writes

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

出力

Sorted array is :
1 3 3 4 4 5 5 6 8

すべての変数はローカルスコープ内で宣言されており、それぞれの参照関係は上図のようになっています。

アルゴリズムのポイント

• 各サイクルの開始位置にある要素が、本来置かれるべき正しい位置（pos）を求めます。
• すでに正しい位置にあれば何もせず、次のサイクルへ進みます。
• 重複した値が存在する場合は、同じ値の直後の位置へずらして配置します。
• 要素を正しい位置に入れたら、空いた位置に入るべき要素を取り出し、サイクルが元の開始位置に戻るまでこの操作を繰り返します。

計算量

サイクルソートの時間計算量は、最良・平均・最悪のいずれのケースでも O(n²) です。一方で、配列への書き込み回数は最大でも n 回程度に抑えられるため、「書き込み回数を最小化したい」という要件がある場合に非常に有効な選択肢となります。

まとめ

この記事では、Pythonでサイクルソートを実装する方法について学びました。サイクルをたどりながら要素を正しい位置へ配置していくこのアルゴリズムは、シンプルでありながら書き込み回数を最小限に抑えられる点が大きな魅力です。ぜひ自分のデータでも動作を確認してみてください。