সাইকেল সর্ট হলো একটি ইন-প্লেস, আনস্টেবল সর্টিং অ্যালগরिदম, একটি কম্পারিজন সর্ট যা থিওরেটিক্যালি অরিজিনাল অ্যারেতে রাইট অপারেশনের মোট সংখ্যা দিয়ে অপ্টিমাল, অন্য যেকোনো ইন-প্লেস সর্টিং অ্যালগরিদমের চেয়ে ভিন্ন। এটি এই আইডিয়ার ওপর ভিত্তি করে যে পারমুটেশনকে সর্ট করতে হবে সেটিকে সাইকেলে ফ্যাক্টর করা যায়, যেগুলো আলাদা আলাদা ঘুরিয়ে সর্টেড রেজাল্ট দিতে পারে।
প্রায় সব সর্টের বিপরীতে, আইটেমগুলো অ্যারেতে কখনো অন্য জায়গায় লেখা হয় না সেটিগুলোকে পাশে ঠেলে দেয়ার জন্য। প্রতিটি ভ্যালু হয় শূন্য বার লেখা হয়, যদি সেটি ইতিমধ্যে তার সঠিক পজিশনে থাকে বা একবার তার সঠিক পজিশনে লেখা হয়। এটি পূরণ ইন-প্লেস সর্টের জন্য প্রয়োজনীয় মিনিমাম ওভাররাইটের সাথে মিলে যায়।
রাইটের সংখ্যা মিনিমাইজ করা তখন কাজে আসে যখন যেকোনো বড় ডেটা সেটে রাইট করা খুব ব্যয়বহুল, যেমন EEPROMs-ye ফ্ল্যাশ মেমরি যেখানে প্রতিটি রাইট মেমরির লাইফস্প্যান কমিয়ে দেয়।
ইনপুট: a[]={7,4,3,5,2,1,6} আউটপুট: 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; }
