[알고리즘] 배열 회전 프로그램

temp에 arr[0]을 저장한 후, 한번씩 회전하는 알고리즘을 구현해서 만드는 방법

#include  
using namespace std; 

void leftRotatebyOne(int arr[], int n){
    int temp = arr[0], i;
    for(i = 0; i < n-1; i++){
        arr[i] = arr[i+1];
    }
    arr[i] = temp;
}

void leftRotate(int arr[], int d, int n){
    for(int i = 0; i < d; i++)
        leftRotatebyOne(arr, n);
}

void printArray(int arr[], int n){
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
}


int main(){
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    leftRotate(arr, 2, n);
    printArray(arr, n);
    
    return 0;
}

이를 확장 시킨 저글링 알고리즘 방법도 알아보자

하나씩 이동하는 것 대신에 gcd를 이용해 집합을 나누어 여러 요소를 한꺼번에 이동시키는 것이다.

arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

배열 요소 3개를 회전시키면, 아래와 같이 집합으로 나누어 한꺼번에 이동하면서 3번만에 원하는 회전 값을 구할 수 있다.

a) arr [] -> { 4 2 3 7 5 6 10 8 9 1 11 12}

b) arr [] -> {4 5 3 7 8 6 10 11 9 1 2 12}

c) arr [] -> {4 5 6  7 8 9 10 11 12 1 2 3 }

#include  
using namespace std; 
  
int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
  
    else
        return gcd(b, a % b); 
} 
  
void leftRotate(int arr[], int d, int n) 
{ 
    for (int i = 0; i < gcd(d, n); i++) { 
        /* move i-th values of blocks */
        int temp = arr[i]; 
        int j = i; 
  
        while (1) { 
            int k = j + d; 
            if (k >= n) 
                k = k - n; 
  
            if (k == i) 
                break; 
  
            arr[j] = arr[k]; 
            j = k; 
        } 
        arr[j] = temp; 
    } 
} 
  
void printArray(int arr[], int size) 
{ 
    for (int i = 0; i < size; i++) 
        cout << arr[i] << " "; 
} 
  
int main() 
{ 
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    // Function calling 
    leftRotate(arr, 2, n); 
    printArray(arr, n); 
  
    return 0; 
}