सर्किल सॉर्ट तत्वों की दी गई सरणी को सॉर्ट करने के लिए एक दिलचस्प सॉर्टिंग एल्गोरिदम है। एल्गोरिथम सरणी के तत्वों की पूरी तरह से तुलना करता है और एक बार एक भाग में तत्वों को क्रमबद्ध करने के बाद, सरणी के दूसरे छोर को लगातार क्रमबद्ध रूप से क्रमबद्ध करें।
उदाहरण
आइए हम एक सरणी के लिए सर्कल सॉर्ट की कल्पना करें। मान लें कि हमारे पास 6 तत्वों के साथ एक सरणी है।
इनपुट:
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