C++

Forum

 
trying to write a rotate function

jayadelgado (15)
I'm trying to write the code for a function that Physically rearranges the elements of array a so that all the elements are shifted towards the back by a specified distance. for example if i have an array that is
a[] = {1,2,3,4,5,6}. i give it a distance that i want to rotate the array, like 3. so the rotate function would alter the array making it a[] = {4,5,6,1,2,3}.

here is what i have so far but i cant get it to work just right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
void rotate(int a[], int size, int distance)
{
	int n = size;
	int d = distance;
	int rot = 0;
	int nrot = 0;
	int* b;

	b = new int[n];

	for (int i = 0; i< n; i++)
	{
		b[i] = a[i];
	}

	for (int i = 0; i < n; i++)
	{
		while (d > n)
		{
			d = d - n;
			if (d <= n)
				break;
		}
		rot = i + d;
		if (rot > n - 1)
		{
			nrot = d - 1;
			nrot = d + nrot;
			rot = rot - nrot;
			a[rot] = b[i];
		}
		a[rot] = b[i];
	}
}
closed account (D80DSL3A)
Wow!

That's quite a contraption!

It can be simplified greatly.
Consider if this would be useful:
b[(i+distance)%size] = a[i];

Edit: Seriously!
The expression in the [] on the left may look strange, but trace it out!

Choose values for size and distance, then trace through for i=0, 1, 2,...
That assignment puts the elements exactly where they belong in array b.
Last edited on
jayadelgado (15)
wow lol thanks a lot! i got it to work and its only like four lines long!
closed account (D80DSL3A)
I'm glad that helped.

Four lines? I got it almost that short:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
// using a 2nd array to cache values
void rotate_ex( int a[], int size, int distance )
{
    int* b = new int[size];
    
    for( int i = 0; i < size; ++i )
        b[(i+distance)%size] = a[i];

    for( int i = 0; i < size; ++i )
        a[i] = b[i];

    delete [] b;// cleanup
}

Maybe if I rewrite it as:
1
2
3
4
5
6
7
 
void rotate_ex( int a[], int size, int distance )
{
    int* b = new int[size];    
    for( int i = 0; i < size; ++i ) b[(i+distance)%size] = a[i];
    for( int i = 0; i < size; ++i ) a[i] = b[i];
    delete [] b;// cleanup
}

Other versions I worked out:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
// rotate "in place" - no 2nd array
void rotate( int a[], int size, int distance )
{
    int firstVal = a[0];

    for( int i = 0; i < distance; ++i )// for distance number of times
        for( int j = 0; j < size; ++j )// rotate one forward
        {
            int secondVal = a[(j+i+1)%size];
            a[(j+i+1)%size] = firstVal;
            firstVal = secondVal;
        }
}

The recursive one is shortest:
1
2
3
4
5
6
7
8
9
10
11
 
// recursive - values are cached in the local variables val.
void rotate_rec( int a[], int size, int distance, int i = 0 )
{
    int val = a[i];

    if( i < size-1 )
        rotate_rec( a, size, distance, i+1 );

    a[(i+distance)%size] = val;
    return;
}

Last edited on
andywestken (4087)
If you want to compare your algorithm with the STL version, see

rotate
http://www.cplusplus.com/reference/algorithm/rotate/

Andy


Topic archived. No new replies allowed.