Sắp xếp theo chu kỳ là một thuật toán sắp xếp tại chỗ, không ổn định, một sắp xếp so sánh là tối ưu về mặt lý thuyết về tổng số lần ghi vào mảng ban đầu, không giống như bất kỳ thuật toán sắp xếp tại chỗ nào khác. Nó dựa trên ý tưởng rằng hoán vị được sắp xếp có thể được tính thành các chu trình, có thể xoay vòng riêng lẻ để đưa ra kết quả được sắp xếp.
Không giống như hầu hết mọi cách sắp xếp khác, các mục không bao giờ được viết ở nơi khác trong mảng chỉ đơn giản là để đẩy chúng ra khỏi đường của hành động. Mỗi giá trị hoặc được viết 0 lần, nếu nó đã ở đúng vị trí của nó hoặc được viết một lần vào đúng vị trí của nó. Điều này khớp với số lần ghi đè tối thiểu cần thiết để sắp xếp tại chỗ đã hoàn thành.
Giảm thiểu số lần ghi rất hữu ích khi việc ghi vào một số tập dữ liệu lớn là rất tốn kém, chẳng hạn như với các EEPROM như bộ nhớ Flash, nơi mỗi lần ghi sẽ làm giảm tuổi thọ của bộ nhớ.
Input: a[]={7,4,3,5,2,1,6}
Output: 1 2 3 4 5 6 7 Giải thích
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 Ví dụ
#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;
}