সাইকেল সর্ট হল একটি ইন-প্লেস, অস্থির বাছাই অ্যালগরিদম, একটি তুলনা বাছাই যা মূল অ্যারেতে লেখার মোট সংখ্যার পরিপ্রেক্ষিতে তাত্ত্বিকভাবে সর্বোত্তম, অন্য যেকোনো ইন-প্লেস বাছাই অ্যালগরিদমের বিপরীতে। এটি এই ধারণার উপর ভিত্তি করে তৈরি করা হয়েছে যে বাছাই করা স্থানচ্যুতিকে চক্রের মধ্যে ফ্যাক্টর করা যেতে পারে, যা একটি সাজানো ফলাফল দেওয়ার জন্য পৃথকভাবে ঘোরানো যেতে পারে।
প্রায় অন্য সব ধরণের থেকে ভিন্ন, আইটেমগুলিকে অ্যারেতে অন্য কোথাও লেখা হয় না যাতে সেগুলিকে অ্যাকশনের পথ থেকে দূরে সরিয়ে দেয়। প্রতিটি মান হয় শূন্য বার লেখা হয়, যদি এটি ইতিমধ্যেই সঠিক অবস্থানে থাকে বা তার সঠিক অবস্থানে একবার লেখা হয়। এটি একটি সম্পূর্ণ ইন-প্লেস সাজানোর জন্য প্রয়োজনীয় ওভাররাইটের ন্যূনতম সংখ্যার সাথে মেলে৷
কিছু বিশাল ডেটা সেটে লেখালেখি করার সময় লেখার সংখ্যা কম করা খুবই ব্যয়বহুল, যেমন ফ্ল্যাশ মেমরির মতো 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;
} 