Home c Cyclic shift of the array

# Cyclic shift of the array

Author

Date

Category

For example, you need to perform a cyclic shift to the right by n elements. And how to perform a cyclic shift to the right by -n elements? What will the array look like?

Just write what is the correct answer:
Array – 1 2 3 4 5
Nudge -2 (negative number) right

Is the correct answer `3 4 5 1 2 `or `3 4 5 2 1 `?

The correct answer is 3 4 5 1 2

update

Cyclic shift right by -2 is the same as rotate left by 2.

There is an amazingly simple algorithm of three `reverse (array, size) `for cyclic shift to the left, which is easy to remember and almost impossible to make mistakes in implementation.

This is how it works with `12345 `(s [] = 12345, size = 5, dist = 2)

``````reverse (s, dist); // 21 | 345
reverse (s + dist, size - dist); // 21 | 543
reverse (s, size); // 34512
``````

Write that Ken Thompson wrote an editor with the function
reverse in 1971, and he claims it was already legendary back then.

P.S.
it so happened that I recently compared the performance of this algorithm, with block permutation shift (which on average requires fewer transfers array elements and I’ve used it before) and was surprised to find that the algorithm on `reverse () `, despite the greater number of memory operations, is even slightly faster.
So I decided to share it.

Most languages ​​probably already have this. For example, in C++ this is `std :: rotate `from `& lt; algorithm & gt; `

``````std :: rotate (& amp; a [first], & amp; a [middle], & amp; a [last ]);
``````

This is then cyclically shifted so that middle becomes the first element. Regarding the shift to the right, to the left: due to the cyclicity, the shift to the right by n elements is a shift to the left by m – n elements, where m is the size of the array.

If you need to write in C (a tutorial assignment, as I understand it?), then you can take the same implementation from the STL as a sample

``````ForwardIterator next = middle;
while (first! = next)
{
swap (* first ++, * next ++);
if (next == last)
next = middle;
else if (first == middle)
middle = next;
}
``````

Roughly speaking, the idea of ​​work is this (shift to the left by 1):

``````1234
2134
2314
2341
``````

``````int [] a = new int [] {236, 267, 973, 357};
int n = 1;
int [] b = new int [a.length];
for (int i = a.length-1; i & gt; = 0; i--) {
if (i + n & gt; = a.length) {
b [i + n-a.length] = a [i];
}
else {
b [i + n] = a [i];
}
}
for (int i: b) {
System.out.println (i);
}
``````

You will get an n (1) shift to the right in the console output.

I will give an example for C #.
I don’t know more clearly or not, I usually write like this. The method can be formatted as an extension. When shiftValue is positive, the shift occurs to the right, when negative, to the left.

``````public static T [] Shift & lt; T & gt; (T [] array, int shiftValue)
{
var newArray = new T [array.Length];
shiftValue - = array.Length;
if (shiftValue & lt; 0)
{
shiftValue * = - 1;
}
for (var i = 0; i & lt; array.Length; i ++)
{
var index = (i + shiftValue)% array.Length;
newArray [i] = array [index];
}
return newArray;
}
``````

I typed from the body, but it seems like this

right

``````for (I = 1; I & lt; = n; I ++)
{
b = [10];
for (j = 10; j & lt; = 0; j = j - 1)
a [j] = [j-1];
a [1] = b;
}
``````

left

``````for (j = 1; j & lt; = n; j ++)
{
int first = a [1];
for (i = 1; i & lt; 10; i ++)
a [i] = a [i + 1];
a [10] = first;
}
``````

This works for me.

``````void array_Rotate_Right (unsigned char * p, unsigned char e) {
unsigned char i, i1;
for (i1 = 0; i1 & lt; e; i1 ++) {
for (i = 6; i & gt; 0; i -) {
p [i] & gt; & gt; = 1;
if ((p [i-1] & amp; 0x1) == 0x1) p [i] + = 128;
}
p [0] & gt; & gt; = 1;
}
}
``````

I don’t know what language you wanted, I’ll write in C++, it will turn out something like this

``````for (int i = / * here is a number, how long is the array * /; i & gt; = 0; i- -)
{
a [i + n] = a [i];
}
```
```

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.