Vector Juggling Rotation

임의의 벡터를 쉬프트 시킬 때 최소한의 메모리를 사용하여 구현할 수 있는데, 이 때 각 백터 원소의 크기 x 2 의 공간만 있으면 되고 연산은 벡터의 길이에 비례하도록 할 수 있다 ( O(n) ). 저글링 연산인데, 예를들어 8개의 원소를 가지는 벡터를 왼쪽으로 2만큼 쉬프트 시키면 아래와 순서와 같다.

1 2 3 4 5 6 7 8 - 임시공간 - 연산횟수

x 2 3 4 5 6 1 8 - 7 - 1 // 1을 왼쪽으로 2만큼 이동 시키고 전에 있던 7을 보관

x 2 3 4 7 6 1 8 - 5 - 2 // 7을 왼쪽으로 2만큼 이동한 공간에 놓고 5를 보관

x 2 5 4 7 6 1 8 - 3 - 3 // ...

3 2 5 4 7 6 1 8 - x - 4

3 x 5 4 7 6 1 2 - 8 - 5

3 x 5 4 7 8 1 2 - 6 - 6

3 x 5 6 7 8 1 2 - 4 - 7

3 4 5 6 7 8 1 2 - x - 8

막상 코드로 짤려니 아주 햇갈렸다 ㅡ.ㅡ;...

#include <stdio.h>
struct vector
{
  char *data;
  int size;
};
void * vec_init (int size)
{
  struct vector *pvec;
  pvec = (struct vector *) malloc (sizeof (struct vector));
  pvec->data = malloc (sizeof (char) * (size + 1));
  *(pvec->data + size) = '\0';
  pvec->size = size;
  return pvec;
}

void vec_free (struct vector *pvec)
{
  free (pvec->data);
  free (pvec);
}

// juggling rotation
void vec_rotate (struct vector *pvec, int shift_by)
{
  char tmp;
  int i, j, k, f, t;
  int cnt = 0;;
  for (i = 0; i < pvec->size - 1; i++)
    {
      j = i;
      k = (pvec->size + j - shift_by) % pvec->size;
      f = *(pvec->data + j);
      do
        {
          k = (pvec->size + j - shift_by) % pvec->size;
          t = *(pvec->data + k);
          *(pvec->data + k) = f;
          cnt++;
          f = t;
          j = k;
        }
      while (j != i);
      if (cnt >= pvec->size)
        break;
    }
  return;
}

int main ()
{
  int i;
  struct vector *pvec = vec_init (20);

  for (i = 0; i < pvec->size; i++)
    *(pvec->data + i) = 'a' + i;

  printf ("%s\n", pvec->data);
  vec_rotate (pvec, 12);
  printf ("%s\n", pvec->data);
  vec_free (pvec);

  return 0;
}

실행시키니 정상동작한다. 다행 ^^;