অ্যারে রোটেশনের জন্য ব্লক সওয়াপ অ্যালগরিদম একটি দক্ষ অ্যালগরিদম যা অ্যারে রোটেশন করতে ব্যবহৃত হয়। এটি O(n) টাইম কমপ্লেক্সিটিতে কাজ করতে পারে।
অ্যারে রোটেশনে, আমাদের একটি অ্যারে arr[] দেওয়া থাকে যার আকার n এবং একটি সংখ্যা k যা রোটেট করার এলিমেন্টের সংখ্যা নির্দেশ করে।
অ্যারে রোটেশনের উদাহরণ −
ইনপুট −
arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (রোটেশনের সংখ্যা.)আউটপুট −
{1, 8, 9, 2, 4, 6}ব্যাখ্যা − রোটেশনে, আমরা একটি এলিমেন্টকে শেষ পজিশনে শিফ্ট করি এবং বাকি এলিমেন্টগুলো এক পজিশন শিফ্ট করি।
ইনডেক্স ০-এর এলিমেন্ট ইনডেক্স n-1-এ শিফ্ট হবে। এবং বাকি এলিমেন্টগুলো আগের ইনডেক্সে শিফ্ট হবে।
ব্লক সওয়াপ অ্যালগরিদম
ব্লক সওয়াপ অ্যালগরিদম অ্যারে রোটেশন পূর্ণ করতে ব্যবহৃত হয়।
অ্যালগরিদম
স্টেপ ১ − অ্যারেকে দুটি সাব-অ্যারেতে ভাগ করুন k-কে বিভাজন বিন্দু ধরে। এগুলো হবে X = arr[0...k-1] এবং Y = arr[k...n-1]।
স্টেপ ২ − নিচের স্টেপগুলো অনুসরণ করুন যতক্ষণ না X এবং Y-এর আকার সমান হয়।
স্টেপ ২.১ − যদি X-এর আকার Y-এর চেয়ে বড় হয়, X কে দুটি অংশ X1 এবং X2-এ ভাগ করুন যেন X1-এর আকার Y-এর আকারের সমান হয়। তারপর সাব-অ্যারে X1 এবং Y সওয়াপ করুন। এটি মূল অ্যারে ফরমেশনকে X1X2Y থেকে YX2X1-এ পরিবর্তন করবে।
স্টেপ ২.২ − যদি Y-এর আকার X-এর চেয়ে বড় হয়, Y কে দুটি অংশ Y1 এবং Y2-এ ভাগ করুন যেন Y2-এর আকার X-এর আকারের সমান হয়। তারপর সাবঅ্যারে X এবং Y2 সওয়াপ করুন। এটি মূল অ্যারে ফরমেশনকে XY1Y2 থেকে Y2Y1X-এ পরিবর্তন করবে।
স্টেপ ৩ − যখন 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
