ISC Practicals and Theory - Cyclic Shift (Using a Class)

A cyclic shift (rotation) of an array moves every element a fixed number of places in one direction, and the elements pushed off one end re-enter at the other end. This note shifts the array to the left by $k$ positions, using a class whose data members hold the array and whose methods do the separate jobs.

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. A shift by $k$ positions is this 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\}$.
• Shifting an array of $n$ elements by $n$ gives back the original, so a shift by $k$ equals a shift by $k \bmod n$. For $n = 5$ and $k = 7$, only $7 \bmod 5 = 2$ shifts are needed.

Algorithm

1. main reads the size size. If it is less than 1 or more than 20, it prints Invalid size and stops.
2. main creates an object ob with new CyclicShift(size). The constructor stores the size in n and creates the array a.
3. ob.accept(sc) reads the n elements into a.
4. main reads k. If it is negative, it prints Invalid shift and stops.
5. ob.shiftLeft(k) does the shift:
   • It replaces k by k % n.
   • It calls shiftOnce() exactly k times.
   • shiftOnce() saves a[0] in first, moves a[i + 1] into a[i] for i from 0 to n - 2, and puts first in a[n - 1].
6. ob.display() prints the array.

Program

The constructor sets up the array, accept() reads the elements, shiftOnce() shifts by one place, shiftLeft() repeats it the right number of times and display() prints the array.

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

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: 5
Enter 5 elements:
1 2 3 4 5
Enter the number of positions to shift left: 7
Array after shifting left by 2 positions:
3 4 5 1 2 

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

Enter the size of the array: 4
Enter 4 elements:
1 2 3 4
Enter the number of positions to shift left: -1
Invalid shift

Dry run

Input: size = 5, array $\{1, 2, 3, 4, 5\}$, k = 7. In shiftLeft, $k = 7 \bmod 5 = 2$.

display() then prints 3 4 5 1 2, which matches the second sample run.

Variations

1. Right shift "Write a program with a class to shift the elements of an array cyclically to the right by k positions."
2. String "Shift the characters of a String cyclically by k places using methods."
3. 2D array "Rotate each row of a matrix by k positions."