C++で実装するサイクルソートのアルゴリズムとサンプルプログラム

サイクルソート（Cycle Sort）は、インプレース（追加メモリをほとんど使わない）かつ非安定な比較ソートアルゴリズムです。最大の特徴は、元の配列への書き込み回数が理論上の最小値になるという点で、これは他のどのインプレースソートアルゴリズムにもない性質です。

このアルゴリズムの基礎となるアイデアは、「ソート対象の順列は複数のサイクル（巡回）に分解でき、それぞれのサイクルを個別に回転させることでソート結果が得られる」というものです。

他のほとんどのソートとは異なり、サイクルソートでは要素を単に「どかす」ために別の場所へ書き込むことが一切ありません。各値は、すでに正しい位置にあれば0回、そうでなければ正しい位置へ1回だけ書き込まれます。これは、インプレースソートを完了するために必要な最小限の上書き回数と一致します。

書き込み回数を最小限に抑えることが有効なのは、EEPROMやフラッシュメモリのように、書き込みのたびにメモリの寿命が縮んでしまう大容量データセットへの書き込みコストが非常に高い場合です。

入力: a[]={7,4,3,5,2,1,6}
出力: 1 2 3 4 5 6 7

アルゴリズムの解説

サイクルソートでは、各サイクルの開始位置から順に、その要素が本来置かれるべき位置を求め、要素を正しい位置へ回転させていきます。以下は配列 {10, 5, 2, 3} をソートする過程のトレースです。

arr[] = {10, 5, 2, 3}
index = 0 1 2 3
cycle_start = 0
item = 10 = arr[0]

item を置くべき位置を探す
pos = cycle_start
while (arr[i] < item)
    pos++

10 を arr[3] へ置き、item を arr[3] の元の値に更新
arr[] = {10, 5, 2, 10}
item = 3

再びインデックス 0 から始まる残りのサイクルを回転
item = 3 を置くべき位置を探し、arr[1] の要素と交換
arr[] = {10, 3, 2, 10}
item = 5

再びインデックス 0 から始まる残りのサイクルを回転し、item = 5
arr[2] の要素と交換
arr[] = {10, 3, 5, 10}
item = 2

再びインデックス 0 から始まる残りのサイクルを回転し、item = 2
arr[] = {2, 3, 5, 10}

以上が cycle_start = 0 の1回分の処理です。
cycle_start = 1, 2, ... n-2 について同様の手順を繰り返します。

C++での実装例

以下は、サイクルソートをC++で実装したサンプルコードです。変数 writes で実際の書き込み回数をカウントできるようにしています。

#include<iostream>
using namespace std;

void cycleSort(int a[], int n) {
    int writes = 0;
    for (int c_start = 0; c_start <= n - 2; c_start++) {
        int item = a[c_start];
        int pos = c_start;
        // item より小さい要素の数から正しい位置を求める
        for (int i = c_start + 1; i < n; i++)
            if (a[i] < item)
                pos++;
        // すでに正しい位置にあればスキップ
        if (pos == c_start)
            continue;
        // 重複要素をスキップ
        while (item == a[pos])
            pos += 1;
        if (pos != c_start) {
            swap(item, a[pos]);
            writes++;
        }
        // サイクルの残りを回転
        while (pos != c_start) {
            pos = c_start;
            for (int i = c_start + 1; i < n; i++)
                if (a[i] < item)
                    pos += 1;
            while (item == a[pos])
                pos += 1;
            if (item != a[pos]) {
                swap(item, a[pos]);
                writes++;
            }
        }
    }
}

int main() {
    int a[] = {7,4,3,5,2,1,6};
    int n = 7;
    cycleSort(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

計算量について

サイクルソートの計算量は以下のとおりです。

• 時間計算量: 最悪・平均・最良のいずれの場合も O(n²)
• 空間計算量: O(1)（インプレース処理のため補助メモリは不要）
• 安定性: 非安定ソート

ソート速度そのものはクイックソートなどの高度なアルゴリズムに劣りますが、書き込み回数が最小限に抑えられるため、フラッシュメモリやEEPROMなど書き込み寿命が限られた記憶媒体を扱う場面で特に有用なアルゴリズムです。