การเรียงลำดับตามรอบคืออัลกอริธึมการจัดเรียงแบบฝังที่ไม่เสถียร ซึ่งเป็นการจัดเรียงแบบเปรียบเทียบที่เหมาะสมที่สุดตามทฤษฎีในแง่ของจำนวนการเขียนทั้งหมดไปยังอาร์เรย์ดั้งเดิม ซึ่งแตกต่างจากอัลกอริธึมการจัดเรียงแบบแทนที่อื่นๆ มันขึ้นอยู่กับแนวคิดที่ว่าการเรียงสับเปลี่ยนที่จะจัดเรียงสามารถแยกตัวประกอบเป็นรอบ ซึ่งสามารถหมุนแยกกันเพื่อให้ได้ผลลัพธ์ที่จัดเรียง
ไม่เหมือนกับการเรียงลำดับอื่น ๆ เกือบทุกรายการ ไอเท็มจะไม่ถูกเขียนไว้ที่อื่นในอาร์เรย์เพียงเพื่อผลักดันให้พวกมันออกจากการกระทำ แต่ละค่าจะถูกเขียนเป็นศูนย์ครั้ง ถ้าค่านั้นอยู่ในตำแหน่งที่ถูกต้องอยู่แล้ว หรือเขียนครั้งเดียวไปยังตำแหน่งที่ถูกต้อง ซึ่งตรงกับจำนวนการเขียนทับขั้นต่ำที่จำเป็นสำหรับการจัดเรียงแบบแทนที่ที่เสร็จสมบูรณ์
การลดจำนวนการเขียนจะมีประโยชน์เมื่อการเขียนข้อมูลขนาดใหญ่บางชุดมีราคาแพงมาก เช่น 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;
} 