7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – vnp Mar 7 '16 at 18:56
  • \$\begingroup\$ @vnp: Thanks, I've fixed it in my answer now. \$\endgroup\$ – Edward Mar 7 '16 at 19:23
  • \$\begingroup\$ @Edward your changed answer does not compile. \$\endgroup\$ – MAG Mar 7 '16 at 19:31
  • 1
    \$\begingroup\$ @MAG: cut-and-paste error. It was missing the line declaring temp but it's fixed now. \$\endgroup\$ – Edward Mar 7 '16 at 19:37
  • \$\begingroup\$ thanks a lot for your help! you have nicely broken down the problem! \$\endgroup\$ – Max Payne Mar 10 '16 at 17:29
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Very elegant. Nice! \$\endgroup\$ – Edward Mar 8 '16 at 0:08
  • \$\begingroup\$ By far, the most elegant and clever solution ! \$\endgroup\$ – Calak Dec 3 '18 at 19:43
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ This is surely more compact, and way more elegant, but isn't efficiency the same? +1 \$\endgroup\$ – Max Payne Mar 7 '16 at 14:12
  • \$\begingroup\$ 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. \$\endgroup\$ – coderodde Mar 7 '16 at 14:14
  • \$\begingroup\$ What is $\Theta(n)$ ? \$\endgroup\$ – Max Payne Mar 7 '16 at 14:18
  • \$\begingroup\$ 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. \$\endgroup\$ – coderodde Mar 7 '16 at 14:21
  • \$\begingroup\$ Your new edit is not working for any value of n or shift! \$\endgroup\$ – Max Payne Mar 7 '16 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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