Shifting or rotating elements is part of a collection of standard algorithms.
Shift/rotate left
Shifting or rotating elements left within an array refers to moving each element 1 position to the left. The original first element of the array becomes the new last element.
Original array:
[5, 6, 7, 8, 9]
Expected result after left shift/rotate:
[6, 7, 8, 9, 5]
Algorithm
If the array is of length 0
Return (stop).
Set temp to the first element.
Loop through every element except the first.
Set the element at i - 1 to the element at i.
Set the last element to temp.
The first check can be omitted if there is a precondition that the array length is at least 1.
The first check could also check if the array length is <= 1. An array of length 1 does not need to be changed. This check has been omitted here since the rest of the code will work with an array of length 1. The loop will not run. The only element will be copied on top of itself.
Implementation in Java
public static void rotateLeft(int[] vals)
{
if(vals.length == 0)
return;
int temp = vals[0];
for(int i = 1; i < vals.length; i++)
{
vals[i - 1] = vals[i];
}
vals[vals.length - 1] = temp;
}
The loop uses i to represent the position the element is at now (before being copied). This makes both the loop and the body easier to write. The position to which the element is copied (i- 1) is in terms of where the element is now (i).
Alternatively, the loop can be written with i as the position to which the element is to be copied.
for(int i = 0; i < vals.length - 1; i++)
{
vals[i] = vals[i + 1];
}
Shift/rotate right
Original array:
[5, 6, 7, 8, 9]
Expected result after right shift/rotate:
[9, 5, 6, 7, 8]
Algorithm
If the array is of length 0
Return (stop).
Set temp to the last element.
Loop backwards through every element except the last.
Set the element at i + 1 to the element at i.
Set the first element to temp.
As with the left rotation, the first check can be omitted if the precondition prevents the situation. Also as with the left rotation, the first check can include a length of 1 if desired.
Implementation in Java
public static void rotateRight(int[] vals)
{
if(vals.length == 0)
return;
int temp = vals[vals.length - 1];
for(int i = vals.length - 2; i >= 0; i--)
{
vals[i + 1] = vals[i];
}
vals[0] = temp;
}
As with the left rotation, i is used to represent the position the element is at now.
Alternatively, the loop can be written such that i represents the position to which the element is to be copied.
for(int i = vals.length - 1; i > 0; i--)
{
vals[i] = vals[i - 1];
}
Help & comments
Get help from AP CS Tutor Brandon Horn