Circle Sort হল একটি আকর্ষণীয় বাছাই করা অ্যালগরিদম যা উপাদানগুলির একটি প্রদত্ত অ্যারে সাজানোর জন্য। অ্যালগরিদম অ্যারের উপাদানগুলিকে ব্যাসামিকভাবে তুলনা করে এবং একবার একটি অংশের উপাদানগুলিকে সাজানো হয়ে গেলে, তারপর ক্রমাগত অ্যারের অন্য প্রান্তটি ব্যাসামিকভাবে সাজান৷
উদাহরণ
আসুন একটি অ্যারের জন্য বৃত্ত সাজানোর কল্পনা করি। ধরা যাক আমাদের কাছে ৬টি উপাদান সহ একটি অ্যারে আছে।
ইনপুট:
N = 6
arr [ ] = { 2, 1, 5, 8, 7, 9 }
যখন আমরা প্রতিটি অ্যারের উপাদানের জন্য এককেন্দ্রিক বৃত্ত আঁকি, তখন এটি নিম্নরূপ প্রদর্শিত হবে
আউটপুট:
1 2 5 7 8 9
ব্যাখ্যা: সার্কেল সর্ট ব্যবহার করে অ্যারের উপাদানগুলি সাজানোর পরে, এটি হবে 1, 2, 5, 7, 8, 9৷
বৃত্ত সাজানোর জন্য অ্যালগরিদম
- অ্যারের প্রথম এলিমেন্টের সাথে শেষ এলিমেন্টের তুলনা করুন, দ্বিতীয় এলিমেন্টের সাথে অ্যারের দ্বিতীয় শেষ এলিমেন্টের তুলনা করুন।
- এখন অ্যারেটিকে দুটি অর্ধে ভাগ করুন এবং তারপরে আবার বৃত্ত সাজানোর ব্যবহার করুন প্রথমার্ধের প্রথম উপাদানটির শেষ উপাদানটির সাথে তুলনা করতে৷
- অ্যারে সাজানো না হওয়া পর্যন্ত পুনরাবৃত্তভাবে ধাপ-1 এবং ধাপ-2 কল করুন।
বৃত্ত সাজানোর জন্য C++ প্রোগ্রাম
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
bool circle_sort_rec(int * arr, int n) {
bool swaped = false;
if (n <= 2) {
if (arr[0] > arr[n - 1]) {
swap(arr[0], arr[n - 1]);
swaped = true;
}
return swaped;
}
int mid = (n + 1) / 2;
for (int i = 0; i < mid; i++) {
if (i == n - i - 1) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swaped = true;
}
} else {
if (arr[i] > arr[n - i - 1]) {
swap(arr[i], arr[n - i - 1]);
swaped = true;
}
}
}
if (circle_sort_rec(arr, mid))
swaped = true;
if (circle_sort_rec(arr + mid, n - mid))
swaped = true;
return swaped;
}
void circle_sort(int * arr, int size) {
while (circle_sort_rec(arr, size)) {
;
}
return;
}
int main() {
int size = 5;
int arr[size] = {2,1,7,4,5,9};
circle_sort(arr, size);
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
return 0;
} আউটপুট
1 2 4 5 7
