current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 6 down vote favorite
1

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.

share|improve this question
up vote 4 down vote

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:

step 0

step 1

step 2

step 3

step 4

step 5

step 6

share|improve this answer
    
This algorithm terminates after rotating a single orbit generated by shift. To rotate the whole array, the loop must be repeated for all orbits, gcd(n, shift) times total. – vnp yesterday
    
@vnp: Thanks, I've fixed it in my answer now. – Edward yesterday
    
@Edward your changed answer does not compile. – MAG yesterday
1  
@MAG: cut-and-paste error. It was missing the line declaring temp but it's fixed now. – Edward yesterday
up vote 2 down vote

(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.

share|improve this answer
    
This is surely more compact, and way more elegant, but isn't efficiency the same? +1 – Tim yesterday
    
Yes, the running time is still linear (i.e., \$\Theta(n)\$). If you want it faster, use a linked list, which could do it in time \$\Theta(m)\$, where \$m\$ is the shift amount. Also, I believe that the operation you do is actually called rotation. – coderodde yesterday
    
What is $\Theta(n)$ ? – Tim yesterday
    
It's a common notation for communicating how efficient an algorithm is. In this case, \$\Theta(n)\$ means that your algorithm runs in linear amount of steps: double the size of the input array to rotate, the running time will double too. For example, efficient sorting is done in \$\Theta(n \log n)\$ time, where \$n\$ is the length of the array. – coderodde yesterday
    
Your new edit is not working for any value of n or shift! – Tim yesterday
up vote 2 down vote

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 ones.

share|improve this answer
    
Very elegant. Nice! – Edward yesterday

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.