Rotation of elements in an array We had to write a program that would perform rotation of elements in an array. The array size was entered by user, so it had to be in a sense, dynamic.

Rotation or Circular Shifting

Initial Array: 1 3 7 4 8 6 5 2 9  

Shift by: 4  

Final Array: 6 5 2 9 1 3 7 4 8

Notice, in rotation, each elements position increased by shift amount. Also, elements in the end came to the front.

My Try

I used an approach in which I had to create a new array of size = shift amount. This array stored the shift no. of elements in the end of array. Now I shifted all the elements in the beginning of array by shift amount. In the end, I copied the elements of shift sized array to beginning of original array. 

I tried to use minimum memory possible so only used shift sized array. I and keep it a bit fast (shift%=n statement to reduce inefficiency if shift >= n).

// Rotation

#include &lt;iostream&gt;

int main() {

    int n;
    std::cout &lt;&lt; "Array size: ";
    std::cin &gt;&gt; n;
    int* list = new int[n];

    std::cout &lt;&lt; "Enter elements:\n";
    for( int i = 0; i &lt; n; ++i) {
        std::cin &gt;&gt; list[i];
    }

    int shift;
    std::cout &lt;&lt; "Shift amount: ";
    std::cin &gt;&gt; shift;

    shift %= n; // to reduce work if shift &gt; n
    int* temp = new int[shift];

    for( int i = n-shift; i &lt; n ; ++i) {
        temp[i-n+shift] = list[i];
    }

    for( int i = n-1; i &gt;= shift; --i) {
        list[i] = list[i-shift];
    }

    for( int i = 0; i &lt; shift; ++i) {
        list[i] = temp[i];
    }

    delete [] temp;

    // Printing
    for( int i = 0; i &lt; n; ++i) {
        std::cout &lt;&lt; list[i] &lt;&lt; "  ";
    }

    delete [] list;
}


Question

My question is that all the optimization that i was able to make were a bit obvious and natural. I wanted to know if there was a significant algorithmic, or memory optimization possible for this problem.

PS

I know there's a function std::rotate available from algorithm, but we had to solve this problem on our own.
I see some things that may help you improve your program.

Separate I/O from calculations

The program has three basic phases.  First, it gets input, then it manipulates that input, and then it produces output.  I would recommend putting the rotation code into a separate function.

Consider signed vs. unsigned

Does it make sense to have a negative array size?  Does it make sense to have a negative shift value?  I'd answer "no" to the first and "yes" to the second question.  For that reason, I'd recommend making n a size_t or unsigned type and also adding code to handle negative rotations.

Rethink your algorithm

The code currently creates a temporary array, but all that's really needed is a single temporary int.  Here's one way to do it:

unsigned gcd(unsigned a, unsigned b) {
    return b == 0 ? a : gcd(b, a % b);
}
void rotate(unsigned n, int shift, int *list) 
{
    if (shift &lt; 0) {
        shift = n -(-shift % n);
    } else {
        shift %= n;
    }
    if (shift == 0) {
        return;
    }
    for (unsigned cycles = gcd(n, shift); cycles; --cycles) {
        unsigned i = 0;
        unsigned nexti = n-shift;
        for (int temp=list[nexti+cycles-1]; nexti; i = nexti) {
            nexti = i+shift;
            if (nexti &gt;= n) {
                nexti -= n;
            }
            std::swap(temp, list[i+cycles-1]);
        }
    }
}


Worked example

This is probably easier to understand with an example.  Let's start with a simple array or length 7 = { 0, 1, 2, 3, 4, 5, 6} and a requested shift amount of 4.  When the for loop starts we have this: