0

Recently I learnt about the array rotation in linear time using Juggling algorithm. Here is the snippet regarding the left rotation of the array.

void ArrayRotate (int A[], int n, int k)
{
  int d=-1,i,temp,j;
  for(i=0;i<gcd(n,k);i++)
  {
    j=i;
    temp=A[i];
    while(1)
    {
      d=(j+k)%n;
      if(d==i)
        break;
      A[j]=A[d];
      j=d;
    }
    A[j]=temp;
  }
}

but now I am stuck as how to use this Juggling algorithm to rotate the array in the Right Direction.

1,2,3,4,5  (given array) 
5,1,2,3,4   (after 1 right rotation)

(I had solved this question using the brute force method and reversal method.)

Improve this question
5
  • Please tag only one language unless the question is about interoperation of the two or differences between them Commented Mar 25, 2020 at 17:58
  • for(i=n-1;i<gcd(n,k);i--) -- Off topic, but you are computing gcd(n,k) on each iteration of your loop. Simply calculate it once, store it in a variable, and use that variable in the for loop. Commented Mar 25, 2020 at 18:17
  • for(i=n-1;i<gcd(n,k);i--) is going to stop immediately, unless n < k and n is a prime factor of k, surely ? Commented Mar 25, 2020 at 18:26
  • @ChrisHall sir, I had corrected the code. Commented Mar 25, 2020 at 20:54
  • @idclev463035818 I had removed duplicate tags Commented Mar 25, 2020 at 20:58

2 Answers 2

Reset to default
1
  1. As already mentioned, you should use std::rotate if you are allowed to.
  2. Your implementation has a bug. Here is a fixed implementation. 
void ArrayRotate(int A[], int n, int k) {
    int d = -1, i, temp, j;
    int g = gcd(n, k);
    for (i = 0; i < g; ++i) {
        j = i;
        temp = A[i];
        while (true) {
            d = (j + k) % n;
            if (d == i) {
                break;
            }
            A[j] = A[d];
            j = d;
        }
        A[j] = temp;
    }
 }

Also note that I took out gcd calculation out of loop condition. It does not technically affect complexity, but it's enough to compute the gcd only once.

To rotate the array k times to the right, just rotate it n - k times to the left. 

void ArrayRotateRight(int A[], int n, int k) {
    ArrayRotate(A, n, n - k);
}

Or change the 8th line to be d = (j - k + n) % n;

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Not sure if you're doing this as an intellectual exercise, or for production code, but for production code use the STL rotate algorithm:

#include<iostream>
#include<algorithm>

using namespace std;

void display(int* a, int length)
{
    for (int i = 0; i < length; ++i)
        cout << a[i] << " ";

    cout << endl;
}

int main()
{
    const int len = 5;

    int arr[] =  { 1,2,3,4,5 };

    display(arr, len);

    rotate(arr, arr + 1, arr + len); // arr + x means left by x

    display(arr, len);

    rotate(arr, arr + len - 1, arr + len); // arr + len - x means right by x 

    display(arr, len);
}
Improve this answer

1 Comment

i solved this question using stl only. but found a cool way here stackoverflow.com/questions/23321216/… and just was wondering how to implement the other way.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.