অ্যারে রোটেশনের জন্য ব্লক অদলবদল অ্যালগরিদম হল একটি দক্ষ অ্যালগরিদম যা অ্যারে রোটেশনের জন্য ব্যবহৃত হয়। এটি 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
