ISC Practicals and Theory - Cyclic Shift

A cyclic shift (also called a rotation) of an array moves every element a fixed number of places in one direction. The elements that fall off one end are not lost: they come back at the other end. This note shifts the array to the left by $k$ positions, using only main.

Definition

In a left cyclic shift by one position, every element moves one place to the left and the first element goes to the end of the array. A shift by $k$ positions is this single shift done $k$ times.

• For $\{1, 2, 3, 4, 5\}$ and $k = 2$: after one shift $\{2, 3, 4, 5, 1\}$, after two shifts $\{3, 4, 5, 1, 2\}$.
• If the array has $n$ elements, shifting by $n$ gives the original array back. So a shift by $k$ is the same as a shift by $k \bmod n$. For $n = 4$ and $k = 7$, we need only $7 \bmod 4 = 3$ shifts.

Algorithm

1. Read the size n. If it is less than 1 or more than 20, print Invalid size and stop.
2. Create the array a of size n and read its n elements with a for loop.
3. Read k. If it is negative, print Invalid shift and stop.
4. Replace k by k % n, because extra full rounds change nothing.
5. Repeat k times (loop variable s):
   • Save the first element a[0] in first.
   • Move each element one place left: for i from 0 to n - 2, do a[i] = a[i + 1].
   • Store first in the last place, a[n - 1].
6. Print the shifted array with a for loop.

Program

The whole program is in main: it reads the data, checks it, does the shifts with two nested loops and prints the result.

import java.util.Scanner;
public class CyclicShift
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the size of the array: ");
        int n = sc.nextInt();
        if (n < 1 || n > 20)
        {
            System.out.println("Invalid size");
            return;
        }
        int a[] = new int[n];
        System.out.println("Enter " + n + " elements:");
        for (int i = 0; i < n; i++)
            a[i] = sc.nextInt();
        System.out.print("Enter the number of positions to shift left: ");
        int k = sc.nextInt();
        if (k < 0)
        {
            System.out.println("Invalid shift");
            return;
        }
        k = k % n;
        for (int s = 1; s <= k; s++)
        {
            int first = a[0];
            for (int i = 0; i < n - 1; i++)
                a[i] = a[i + 1];
            a[n - 1] = first;
        }
        System.out.println("Array after shifting left by " + k + " positions:");
        for (int i = 0; i < n; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
}

Variable description table

Sample input and output

Enter the size of the array: 5
Enter 5 elements:
1 2 3 4 5
Enter the number of positions to shift left: 2
Array after shifting left by 2 positions:
3 4 5 1 2 

Enter the size of the array: 4
Enter 4 elements:
10 20 30 40
Enter the number of positions to shift left: 7
Array after shifting left by 3 positions:
40 10 20 30 

Enter the size of the array: 3
Enter 3 elements:
5 6 7
Enter the number of positions to shift left: 0
Array after shifting left by 0 positions:
5 6 7 

Enter the size of the array: 0
Invalid size

Dry run

Input: n = 5, array $\{1, 2, 3, 4, 5\}$, k = 2. Since $2 \bmod 5 = 2$, k stays 2.

After the loop ends the array is printed as 3 4 5 1 2.

Variations

1. Right shift "Write a program to shift the elements of an array cyclically to the right by k positions."
2. Using methods "Write a program with a class that has methods to accept the array, shift it by k places and display it."
3. Matrix rows "Shift each row of a matrix cyclically by k positions."
4. String "Shift the characters of a String cyclically by k places."