배열 회전을 위한 블록 스왑 알고리즘은 배열 회전에 사용되는 효율적인 알고리즘입니다. O(n) 시간 복잡도에서 작업을 수행할 수 있습니다.
따라서 배열 회전에서 크기가 n인 배열 arr[]와 아니오를 정의하는 숫자 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> Y이면 X1의 크기가 Y의 크기와 같도록 X를 두 부분 X1과 X2로 나눕니다. 그런 다음 하위 배열 X1과 Y를 교체합니다. 그러면 원래 배열 구성이 X1X2Y에서 다음으로 변경됩니다. YX2X1.
2.2단계 − Y의 크기가 X> X이면 Y2의 크기가 X의 크기와 같도록 Y를 두 부분 Y1과 Y2로 나눕니다. 그런 다음 하위 배열 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