サイクルソート用のC++プログラム？

サイクルソートは、インプレースの不安定なソートアルゴリズムであり、他のインプレースソートアルゴリズムとは異なり、元の配列への書き込みの総数に関して理論的に最適な比較ソートです。これは、並べ替えられる順列をサイクルに分解でき、個別にローテーションして並べ替えられた結果を得ることができるという考えに基づいています。

他のほとんどすべての種類とは異なり、アイテムは、単にアクションの邪魔にならないようにするために、配列の他の場所に書き込まれることはありません。各値は、すでに正しい位置にある場合は0回書き込まれるか、正しい位置に1回書き込まれます。これは、インプレースソートの完了に必要な上書きの最小数と一致します。

書き込み回数を最小限に抑えることは、フラッシュメモリなどのEEPROMを使用する場合など、書き込みごとにメモリの寿命が短くなるなど、巨大なデータセットへの書き込みに非常に費用がかかる場合に役立ちます。

Input: a[]={7,4,3,5,2,1,6}
Output: 1 2 3 4 5 6 7

説明

arr[] = {10, 5, 2, 3}
index = 0 1 2 3
cycle_start = 0
item = 10 = arr[0]
Find position where we put the item,
pos = cycle_start
while (arr[i] < item)
pos++;
We put 10 at arr[3] and change item to
old value of arr[3].
arr[] = {10, 5, 2, 10}
item = 3
Again rotate rest cycle that start with index '0'
Find position where we put the item = 3
we swap item with element at arr[1] now
arr[] = {10, 3, 2, 10}
item = 5
Again rotate rest cycle that start with index '0' and item = 5
we swap item with element at arr[2].
arr[] = {10, 3, 5, 10 }
item = 2
Again rotate rest cycle that start with index '0' and item = 2
arr[] = {2, 3, 5, 10}
Above is one iteration for cycle_stat = 0.
Repeat above steps for cycle_start = 1, 2, ..n-2

例

#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;
      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;
}