Thuật toán hoán đổi khối (Block Swap Algorithm) cho xoay mảng là thuật toán hiệu quả, thực hiện xoay mảng trong độ phức tạp thời gian O(n).
Trong xoay mảng, cho mảng arr[] kích thước n và số k xác định số phần tử cần xoay.
Ví dụ xoay mảng
Đầu vào** –
arr[] = {4, 6, 1, 8, 9, 2}, k = 2
Đầu ra** –
{1, 8, 9, 2, 4, 6}
Giải thích** – Xoay trái: phần tử chỉ số 0 dịch đến chỉ số n-1, các phần tử còn lại dịch trái một vị trí.
Thuật toán Block Swap
Thuật toán hoán đổi khối thực hiện xoay mảng hoàn hảo.
Thuật toán
Bước 1** – Chia mảng thành hai mảng con tại điểm k: X = arr[0...k-1], Y = arr[k...n-1].
Bước 2** – Lặp cho đến khi kích thước X và Y bằng nhau:
- 2.1** Nếu |X| > |Y|: chia X thành X1, X2 với |X1| = |Y|. Hoán đổi X1 và Y. Mảng từ X1 X2 Y thành Y X2 X1.
- 2.2** Nếu |Y| > |X|: chia Y thành Y1, Y2 với |Y2| = |X|. Hoán đổi X và Y2. Mảng từ X Y1 Y2 thành Y2 Y1 X.
Bước 3** – Khi |X| = |Y|, hoán đổi chúng.
Thuật toán cần gọi đệ quy hoặc lặp. Ta thảo luận cả hai cách.
Ví dụ – Đệ quy
#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 << "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ụ – Lặp
#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