सरणी रोटेशन के लिए ब्लॉक स्वैप एल्गोरिदम एक कुशल एल्गोरिदम है जिसका उपयोग सरणी रोटेशन के लिए किया जाता है। यह O(n) समय जटिलता में आपका काम कर सकता है।
तो, सरणी रोटेशन में, हमें आकार n की एक सरणी गिरफ्तारी [] और एक संख्या k दी जाती है जो संख्या को परिभाषित करती है। घुमाए जाने वाले तत्व का।
आइए सरणी घुमावों पर एक उदाहरण देखें -
इनपुट -
arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (number of rotations.) आउटपुट -
{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 का आकार समान हो, तो उन्हें स्वैप करें।
इस एल्गोरिथम को कोड के एक ही हिस्से के लिए एक दोहरावदार कॉल की आवश्यकता होती है। यह दोहराव कॉल दो दृष्टिकोणों का उपयोग करके प्राप्त किया जा सकता है। वे पुनरावर्ती दृष्टिकोण . हैं और पुनरावर्ती दृष्टिकोण . हम कार्यक्रमों का उपयोग करके दृष्टिकोण पर चर्चा करेंगे।
उदाहरण
पुनरावर्ती दृष्टिकोण को दर्शाने के लिए कार्यक्रम -
#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, intk){
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<<"Array before rotations :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
blockSwapAlgo(arr, k, size);
cout<<"\nArray after rotating "<<k<<" times :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
return 0;
} आउटपुट
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 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<<"Array before rotations :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
blockSwapAlgoIt(arr, k, size);
cout<<"\nArray after rotating "<<k<<" times :\t";
for(int i = 0; i<size; i++)
cout<<arr[i]<<" ";
return 0;
} आउटपुट
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 8 9 2 4 6 1