Rotation of elements in an array

Question

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 <iostream>

int main() {

    int n;
    std::cout << "Array size: ";
    std::cin >> n;
    int* list = new int[n];

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

    int shift;
    std::cout << "Shift amount: ";
    std::cin >> shift;

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

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

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

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

    delete [] temp;

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

    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.

Answer 1

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 < 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 >= 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:

Answer 2

You should divide your solution into functions. Also you could implement a rotate function with templates.

---

Alternative

A solution easier and a lot more simple ( Also O(n) in time and O(1) in space) is using a reverse function. Example:

void reverse(int* begin, int* end) {
    while (begin <-- end) {
        std::swap(*begin++, *end);
    }
}

void rotate(int* begin, int* end, int k) {
    int N = end - begin;
    int shift = k % N;
    if (shift < 0) shift += N;

    reverse(begin, end);
    reverse(begin, begin + shift);
    reverse(begin + shift, end);

}

Using the reverse function in the standard library and templates you get:

template<typename R>
void rotate(R begin, R end, int k) {

    int N = end - begin;
    int shift = k % N;
    if (shift < 0) shift += N;

    std::reverse(begin, end);
    std::reverse(begin, begin + shift);
    std::reverse(begin + shift, end);
}

Algorithm example

Suppose you want to rotate (1,2,3,4,5,6,7) by 3.

First you reverse the whole input:

(7,6,5,4,3,2,1)

Then reverse the range [0, 3)

(5,6,7,4,3,2,1)

and finally reverse the range [3, 7) resulting in

(5,6,7,1,2,3,4)

Since reverse does floor(N / 2) swaps this solution traverses the input only once.

Answer 3

(2nd attempt.)

The most efficient data structure for this problem is as follows: (1) basically, you create an array based list with (2) field size which caches the amount of elements in the list, (3) field head which is the index into the "first" element in the list.

Now, with minor bookkeeping you can "rotate" simply by assigning an appropriate value to the head field: runs in constant time and space.