【C++】サークルソート（Circle Sort）の仕組みと実装方法を徹底解説

サークルソート（Circle Sort）とは

サークルソートは、与えられた配列の要素を並べ替えるためのユニークなソートアルゴリズムの一つです。最大の特徴は、配列の先頭と末尾のように「直径上で対になる位置」にある要素同士を比較・交換していく点にあります。片側の部分が整列すると、今度は配列を半分に分割しながら、もう一方の端も同じ要領で再帰的に整列させていきます。

サークルソートの動作例

ここでは、6つの要素を持つ配列を使って、サークルソートの流れを視覚的に確認してみましょう。

入力：

N = 6
arr[ ] = { 2, 1, 5, 8, 7, 9 }

各配列要素を同心円上に配置して描くと、次のようなイメージになります。

出力：

1 2 5 7 8 9

解説：サークルソートによって配列内の要素を並べ替えると、最終的に 1, 2, 5, 7, 8, 9 の順に整列します。

サークルソートのアルゴリズム

• 配列の最初の要素と最後の要素、2番目の要素と後ろから2番目の要素というように、対になる位置の要素同士を比較し、必要であれば交換します。
• 次に配列を前半と後半の2つに分割し、前半部分に対しても同様に、先頭の要素と末尾の要素を比較するサークルソートを適用します。
• 配列全体が完全に整列するまで、手順1と手順2を再帰的に繰り返します。

計算量の目安

サークルソートの平均比較回数は O(n log n)、最悪ケースでは O(n log² n) 程度になるとされています。実装がシンプルで、ほぼ整列済みのデータに対しては少ない交換回数で済むという特徴があります。

C++によるサークルソートの実装

以下は、C++でサークルソートを実装したサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;
bool circle_sort_rec(int * arr, int n) {
    bool swaped = false;
    if (n <= 2) {
        if (arr[0] > arr[n - 1]) {
            swap(arr[0], arr[n - 1]);
            swaped = true;
        }
        return swaped;
    }
    int mid = (n + 1) / 2;
    for (int i = 0; i < mid; i++) {
        if (i == n - i - 1) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swaped = true;
            }
        } else {
            if (arr[i] > arr[n - i - 1]) {
                swap(arr[i], arr[n - i - 1]);
                swaped = true;
            }
        }
    }
    if (circle_sort_rec(arr, mid))
        swaped = true;
    if (circle_sort_rec(arr + mid, n - mid))
        swaped = true;
    return swaped;
}

void circle_sort(int * arr, int size) {
    while (circle_sort_rec(arr, size)) {
        ;
    }
    return;
}

int main() {
    const int size = 6;
    int arr[size] = {2, 1, 7, 4, 5, 9};
    circle_sort(arr, size);
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    return 0;
}

実行結果

1 2 4 5 7 9

プログラムを実行すると、配列 {2, 1, 7, 4, 5, 9} が昇順に整列され、「1 2 4 5 7 9」と出力されます。circle_sort_rec() 関数は1回の走査で実際に交換が行われたかどうかを返し、交換が一切なくなるまで circle_sort() 関数が繰り返し呼び出すことで、確実に整列を完了させる仕組みです。