순환 정렬은 다른 내부 정렬 알고리즘과 달리 원래 배열에 대한 총 쓰기 수의 관점에서 이론적으로 최적인 비교 정렬인 내부 불안정 정렬 알고리즘입니다. 이는 정렬할 순열을 사이클로 분해할 수 있다는 아이디어를 기반으로 하며, 사이클은 개별적으로 회전하여 정렬된 결과를 얻을 수 있습니다.
거의 모든 다른 종류와 달리 항목은 단순히 작업을 방해하기 위해 배열의 다른 곳에 기록되지 않습니다. 각 값은 이미 올바른 위치에 있는 경우 0번 기록되거나 올바른 위치에 한 번 기록됩니다. 이것은 완전한 내부 정렬에 필요한 최소 덮어쓰기 횟수와 일치합니다.
쓰기 횟수를 최소화하는 것은 쓰기가 메모리의 수명을 단축시키는 플래시 메모리와 같은 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;
}