Thuật toán hoán đổi khối để xoay mảng là một thuật toán hiệu quả được sử dụng để xoay mảng. Nó có thể thực hiện công việc của bạn với độ phức tạp về thời gian là O (n).
Vì vậy, trong phép quay mảng, chúng ta được cung cấp một mảng arr [] có kích thước n và một số k xác định giá trị không. của phần tử được xoay.
Hãy xem một ví dụ về xoay mảng -
Đầu vào -
arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (number of rotations.) Đầu ra -
{1, 8, 9, 2, 4, 6} Giải thích - Khi xoay, chúng tôi sẽ chuyển một phần tử đến vị trí cuối cùng và chuyển các phần tử tiếp theo đến một vị trí.
Phần tử ở chỉ mục 0 sẽ được chuyển sang chỉ mục n-1. Và phần còn lại của các phần tử được chuyển sang chỉ mục trước đó.
Thuật toán hoán đổi khối
Thuật toán hoán đổi khối được sử dụng để thực hiện xoay mảng một cách hoàn hảo.
Thuật toán
Bước 1 - Chia mảng hai mảng con với k là điểm chia. Gọi chúng là X =arr [0 ... k-1] và Y =arr [k ... n-1].
Bước 2 - Thực hiện theo các bước dưới đây cho đến khi kích thước của X và Y bằng nhau.
Bước 2.1 - Nếu kích thước của X> Y, hãy chia X thành hai phần X1 và X2 sao cho kích thước của X1 bằng kích thước của Y. Sau đó hoán đổi mảng con X1 và Y. Điều này sẽ thay đổi cách hình thành mảng ban đầu từ X1X2Y thành YX2X1.
Bước 2.2 - Nếu kích thước của Y> X, chia Y thành hai phần Y1 và Y2 sao cho kích thước của Y2 bằng kích thước của X. Sau đó hoán đổi mảng con X và Y2. Điều này sẽ thay đổi cấu trúc mảng ban đầu từ XY1Y2 thành Y2Y1X.
Bước 3 - Khi kích thước của X và Y bằng nhau, hãy hoán đổi chúng.
Thuật toán này cần một lệnh gọi lặp lại đến cùng một đoạn mã. Cuộc gọi lặp đi lặp lại này có thể đạt được bằng hai cách tiếp cận. Chúng là cách tiếp cận đệ quy và phương pháp lặp lại . chúng ta sẽ thảo luận về cách tiếp cận bằng cách sử dụng các chương trình.
Ví dụ
Chương trình minh họa Phương pháp tiếp cận đệ quy -
#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;
} Đầu ra
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 8 9 2 4 6 1
Ví dụ
Chương trình minh họa Phương pháp tiếp cận lặp lại -
#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;
} Đầu ra
Array before rotations : 4 6 1 8 9 2 Array after rotating 3 times : 8 9 2 4 6 1