[씨] o (n) 복잡도에서 설정된 위치 수만큼 배열을 왼쪽 또는 오른쪽으로 회전

Programming Pearls Column 2의 Jon Bentley는 가장 우아하고 효율적인 솔루션으로 알려진 것을 설명합니다.

회전 알고리즘은 reverse()배열의 하위 시퀀스를 반대로 하는 함수 를 사용합니다 . 칼럼에서 인용 :

문제를 배열 ab을 배열 로 변환하는 ba것으로 보겠습니다.하지만 배열 의 지정된 부분에있는 요소를 반전시키는 함수가 있다고 가정 해 보겠습니다. ab로 시작하여 a를 뒤집어 a_r b를, b를 반대로 a_r b_r을 얻은 다음 모든 것을 뒤집어 (a_r b_r) _r을 얻습니다. 정확히 ba입니다.

이것이 당신이 필요로하는 것입니다. 사용자의 입력은 배열을 두 블록 A와 B로 분할 할 위치를 정의합니다. 다음은 제 구현입니다.

void reverse(int a[], int sz) {
  int i, j;
    for (i = 0, j = sz; i < j; i++, j--) {
        int tmp = a[i];
            a[i] = a[j];
                a[j] = tmp;
                  }
                  }
                  
                  void rotate(int array[], int size, int amt) {
                    if (amt < 0)
                        amt = size + amt;
                          reverse(array, size-amt-1);
                            reverse(array+size-amt, amt-1);
                              reverse(array, size-1);
                              }
                              

나는 그것을 테스트했고 작동하고 있습니다. 또한 음의 회전이 처리되는 방식에 유의하십시오. size요소 배열을 amt왼쪽으로 (즉, 음수 값으로) 회전하는 size+amt것은 오른쪽 으로 회전하는 것과 같습니다 .

우아한 코드를 즐기고 댓글에 크레딧을 포함하는 것을 잊지 마십시오 (물론 Jon Bentley에게).

-------------------

오른쪽 회전 사용 :

temp[0]=a[0];
for(i=1;i<=n;i++)
{
    temp[i%2]=a[(i*d)%n];
        a[(i*d)%n]=temp[(i+1)%2];
        }
        

왼쪽 회전 사용 :

temp[0]=a[0];
for(i=1;i<=n;i++)
{
    temp[i%2]=a[(i*(n-d))%n];
        a[(i*(n-d))%n]=temp[(i+1)%2];
        }
        

여기서 a [n]은 배열이고 d는 회전하려는 위치의 수입니다.

-------------------

요소 위치를 바꾸는 것입니다. 위치 1의 요소는 위치 6에 배치되고 그 반대의 경우도 마찬가지입니다. 마지막 부분을 다시 작성해야합니다. 두 가지 방법이 있습니다.

• 새 배열을 할당하고 값을 하나씩 복사하십시오.
• 하나의 값을 tmp에 저장하고 다른 값을 이동하십시오.

-------------------

사소한 접근 방식은 회전하는 것이지만 그 이상을 살펴보면 배열 / 목록의 요소 위치를 변경하는 것은 어떨까요?

def circularArrayRotation(a, k):
    k=k%len(a)
        b=a[len(a)-k:len(a)]
            #print(b)
                a=b+a[0:len(a)-k]
                    print(a)
                    

그건 오른쪽 회전, 왼쪽 회전은 그냥 뒤집기

b=a[k:len(a)] and a=b+a[0:k]

출처
https://stackoverflow.com/questions/22079960