C++でのサークルソート

Circle Sortは、特定の要素の配列を並べ替える興味深い並べ替えアルゴリズムです。アルゴリズムは、配列の要素を直径方向に比較し、一方の部分の要素が並べ替えられると、配列のもう一方の端を直径方向に連続的に並べ替えます。

例

配列の円の並べ替えを視覚化してみましょう。 6つの要素を持つ配列があるとしましょう。

入力：

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

配列要素ごとに同心円を描くと、次のように表示されます

出力：

1 2 5 7 8 9

説明： Circle Sortを使用して配列内の要素を並べ替えると、1、2、5、7、8、9になります。

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

• 配列の最初の要素を最後の要素と比較し、2番目の要素を配列の最後から2番目の要素と比較します。
• 次に、配列を2つに分割してから、もう一度円の並べ替えを使用して、前半の最初の要素とその最後の要素を比較します。
• 配列が並べ替えられるまで、ステップ1とステップ2を再帰的に呼び出します。

サークルソートを実装する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() {
   int size = 5;
   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