サイクルソートとは？計算量・アルゴリズム・C++実装例をわかりやすく解説

サイクルソートとは

サイクルソート（Cycle Sort）は、インプレース型（追加メモリをほとんど使わない方式）のソートアルゴリズムの一つです。要素同士を比較しながら並べ替える比較ベースのソートであり、他のインプレース型ソート手法に対しても効率的に動作します。

最大の特徴は、ソートを完了するために必要なメモリへの書き込み回数が理論上最小であるという点です。このため、EEPROMやフラッシュメモリのように書き込み回数に制約がある記憶媒体を扱うシステムで特に有用とされています。

サイクルソートの計算量

• 時間計算量：O(n²)
• 空間計算量：O(1)

入力と出力

入力：
ソートされていないデータ列：23 63 98 74 20 14 36 45 99 78

出力：
ソート前の配列：23 63 98 74 20 14 36 45 99 78
ソート後の配列：14 20 23 36 45 63 74 78 98 99

アルゴリズム

サイクルソートは cycleSort(array, size) の形式で呼び出します。

入力：ソート対象の配列と、配列内の全要素数
出力：ソート済みの配列

Begin
    for start := 0 to n – 2 do
        key := array[start]
        location := start
        for i := start + 1 to n-1 do
            if array[i] < key then
                location := location + 1
        done

        if location = start then
            ignore lower part, go for next iteration
        while key = array[location] do
            location := location + 1
        done

        if location ≠ start then
            swap array[location] with key
        while location ≠ start do
            location := start
            for i := start + 1 to n-1 do
                if array[i] < key then
                    location := location + 1
            done

            while key = array[location]
                location := location + 1
            if key ≠ array[location]
                swap array[location] and key
        done
    done
End

アルゴリズムのポイント

サイクルソートでは、各要素について「自分より小さい要素の個数」を数えることで、その要素が最終的に配置されるべき正しい位置を求めます。要素を正しい位置へ移動すると、そこに元々あった要素が新しい「key」となり、同じ手順をサイクルが閉じるまで繰り返します。また、重複した値が存在する場合は同一要素の上書きを避けることで、無駄な書き込みを抑えています。

C++による実装例

#include<iostream>
using namespace std;

void swapping(int &a, int &b) {     //aとbの内容を入れ替える
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void cycleSort(int *array, int n) {
    for(int start = 0; start<n-1; start++) {     //配列の要素を正しい位置へ配置する
        int key = array[start];
        int location = start;

        for(int i = start+1; i<n; i++) { //keyより小さい要素の数を右側でカウント
            if(array[i] < key)
                location++;
        }

        if(location == start) //すでに正しい位置なら次の反復へ
            continue;
        while(key == array[location]) //同じデータが見つかったら位置を進める
            location++;
        if(location != start)
            swapping(array[location], key);

        while(location != start) {
            location = start;

            for(int i = start+1; i<n; i++) { //要素を配置するべき位置を求める
                if(array[i] < key)
                    location++;
            }

            while(key == array[location]) //同じデータが見つかったら位置を進める
                location++;
            if(key != array[location])
                swapping(key, array[location]);
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n]; //指定された要素数で配列を作成
    cout << "Enter elements:" << endl;

    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }

    cout << "Array before Sorting: ";
    display(arr, n);
    cycleSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 10
Enter elements:
23 63 98 74 20 14 36 45 99 78
Array before Sorting: 23 63 98 74 20 14 36 45 99 78
Array after Sorting: 14 20 23 36 45 63 74 78 98 99