सरणी रोटेशन के लिए ब्लॉक स्वैप एल्गोरिदम एक कुशल एल्गोरिदम है जिसका उपयोग सरणी रोटेशन के लिए किया जाता है। यह आपका काम O(n) समय जटिलता में कर सकता है।
तो, सरणी रोटेशन में, हमें आकार n की एक सरणी arr[] और एक संख्या k दी जाती है जो रोटेट किए जाने वाले तत्वों की संख्या को परिभाषित करती है।
सरणी रोटेशन पर उदाहरण -
इनपुट -
arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (रोटेशन की संख्या.)
आउटपुट -
{1, 8, 9, 2, 4, 6}
व्याख्या - रोटेशन पर, हम एक तत्व को अंतिम स्थिति में शिफ्ट करेंगे और अगले तत्वों को एक स्थिति शिफ्ट करेंगे।
इंडेक्स 0 पर तत्व इंडेक्स n-1 पर शिफ्ट होगा। और बाकी तत्व पिछले इंडेक्स पर शिफ्ट होंगे।
ब्लॉक स्वैप एल्गोरिदम
ब्लॉक स्वैप एल्गोरिदम का उपयोग सरणी रोटेशन को पूरी तरह से करने के लिए किया जाता है।
एल्गोरिदम
चरण 1 - सरणी को k को विभाजन बिंदु मानकर दो उप-सरणियों में विभाजित करें। मान लें वे X = arr[0...k-1] और Y = arr[k...n-1] हैं।
चरण 2 - नीचे दिए गए चरणों का पालन करें जब तक X और Y का आकार समान न हो जाए।
चरण 2.1 - यदि X का आकार > Y है, तो X को दो भागों X1 और X2 में विभाजित करें ताकि X1 का आकार Y के आकार के बराबर हो। फिर उप-सरणी X1 और Y को स्वैप करें। यह मूल सरणी निर्माण को X1X2Y से YX2X1 में बदल देगा।
चरण 2.2 - यदि Y का आकार > X है, तो Y को दो भागों Y1 और Y2 में विभाजित करें ताकि Y2 का आकार X के आकार के बराबर हो। फिर उप-सरणी X और Y2 को स्वैप करें। यह मूल सरणी निर्माण को XY1Y2 से Y2Y1X में बदल देगा।
चरण 3 - जब X और Y का आकार समान हो जाए, तो उन्हें स्वैप करें।
इस एल्गोरिदम को कोड के उसी हिस्से को बार-बार कॉल करने की आवश्यकता होती है। इस दोहराव कॉल को दो दृष्टिकोणों का उपयोग करके प्राप्त किया जा सकता है। वे पुनरावर्ती दृष्टिकोण (recursive approach) और पुनरावृत्त दृष्टिकोण (iterative approach) हैं। हम प्रोग्राम का उपयोग करके दृष्टिकोण पर चर्चा करेंगे।
कार्यक्रम उदाहरण (पुनरावर्ती दृष्टिकोण)
#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, int k){
int temp;
for(int i = 0; i < k; i++){
temp = arr[start + i];
arr[start + i] = arr[end + i];
arr[end + i] = temp;
}
}
void blockSwapAlgo(int arr[], int k, int n) {
if(k == 0 || k == n)
return;
if(k < (n-k)) {
swapSubArray(arr, 0, (n-k), k);
blockSwapAlgo(arr, k, (n-k));
}
else if(k > (n-k)){
swapSubArray(arr, 0, k, (n-k));
blockSwapAlgo((arr+n-k), (2*k-n), k);
}
else{
swapSubArray(arr, 0, (n-k), k);
return;
}
}
int main() {
int arr[] = {4, 6, 1, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "रोटेशन से पहले सरणी :\t";
for(int i = 0; i<size; i++)
cout << arr[i] << " ";
blockSwapAlgo(arr, k, size);
cout << "\n" << k << " बार रोटेट करने के बाद सरणी :\t";
for(int i = 0; i<size; i++)
cout << arr[i] << " ";
return 0;
}
आउटपुट
रोटेशन से पहले सरणी : 4 6 1 8 9 2 3 बार रोटेट करने के बाद सरणी : 8 9 2 4 6 1
कार्यक्रम उदाहरण (पुनरावृत्त दृष्टिकोण)
#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, int k){
int temp;
for(int i = 0; i < k; i++){
temp = arr[start + i];
arr[start + i] = arr[end + i];
arr[end + i] = temp;
}
}
void blockSwapAlgoIt(int arr[], int k, int size) {
int i, j;
if(k == 0 || k == size)
return;
i = k;
j = size - k;
while (i != j) {
if(i < j){
swapSubArray(arr, k-i, k+j-i, i);
j -= i;
}
else{
swapSubArray(arr, k-i, k, j);
i -= j;
}
}
swapSubArray(arr, k-i, k, i);
}
int main() {
int arr[] = {4, 6, 1, 8, 9, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "रोटेशन से पहले सरणी :\t";
for(int i = 0; i<size; i++)
cout << arr[i] << " ";
blockSwapAlgoIt(arr, k, size);
cout << "\n" << k << " बार रोटेट करने के बाद सरणी :\t";
for(int i = 0; i<size; i++)
cout << arr[i] << " ";
return 0;
}
आउटपुट
रोटेशन से पहले सरणी : 4 6 1 8 9 2 3 बार रोटेट करने के बाद सरणी : 8 9 2 4 6 1