সার্কেল সর্ট একটি অনন্য সর্টিং অ্যালগরিদম যা অ্যারেটিকে ডায়ামেট্রিক্যালি তুলনা করে। প্রথম-শেষ, دوم-শেষের পূর্বের... এইভাবে সর্ট করে।
অ্যালগরিদম
- অ্যারেতে প্রথম এবং শেষ এলিমেন্ট তুলনা করুন, বড় হলে সওয়াপ।
- অ্যারেকে দুটি হälফে ভাগ করুন এবং রিকার্সিভলি সার্কেল সর্ট করুন।
- যতক্ষণ সওয়াপ হয় না, ততক্ষণ চলুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
bool circleSortRec(int* arr, int n) {
bool swapped = false;
if (n <= 2) {
if (arr[0] > arr[n-1]) { swap(arr[0], arr[n-1]); swapped = true; }
return swapped;
}
int mid = (n + 1) / 2;
for (int i = 0; i < mid; i++) {
int j = n - i - 1;
if (i == j) { // মিডল এলিমেন্ট (অড সাইজের জন্য)
if (i+1 < n && arr[i] > arr[i+1]) { swap(arr[i], arr[i+1]); swapped = true; }
} else if (arr[i] > arr[j]) {
swap(arr[i], arr[j]); swapped = true;
}
}
if (circleSortRec(arr, mid)) swapped = true;
if (circleSortRec(arr + mid, n - mid)) swapped = true;
return swapped;
}
void circleSort(int* arr, int n) {
while (circleSortRec(arr, n));
}
int main() {
int arr[] = {2, 1, 7, 4, 5, 9};
int n = 6;
circleSort(arr, n);
for (int x : arr) cout << x << " ";
return 0;
}
আউটপুট
1 2 4 5 7 9
