Array Circular Shift

The problem is to rotate elements in an array in a circular way. For example, shifting the array
{38, 27, 43, 3, 9, 82, 10}
3 positions to the left produces
{3, 9, 82, 10, 38, 27, 43}

Using a loop we can shift elements one position to the left.

public static void shift(int[] arr)
{
    int tmp = arr[0];
    for (int i = 1; i < arr.length; i++)
        arr[i - 1] = arr[i];
    arr[arr.length - 1] = tmp;
}

Using a nested loop, we can shift elements k position to the left.

public static void shift(int[] arr, int k)
{
    k = k % arr.length;
    while (k-- > 0)
    {
        int tmp = arr[0];
        for (int i = 1; i < arr.length; i++)
            arr[i - 1] = arr[i];
        arr[arr.length - 1] = tmp;
    }
}

For an array of length n, the running time of the nested loop above is O(n^2), since k in general is in the order of n.

The following algorithm solves the problem in linear time O(n). It does the following: (1) reverse the array; (2) reverse the first n-k elements; (3) reverse the last k elements. The first step moves the first k elements move to the end, and the next two steps put elements in the right order.

public static void shift(int[] arr, int k)
{
    int n = arr.length;
    k = k % n;
    reverse(arr, 0, n - 1);
    reverse(arr, 0, n - k - 1);
    reverse(arr, n - k, n - 1);
}
public static void reverse(int[] arr, int start, int end)
{
    while (start < end)
    {
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
        start++;
        end--;
    }
}

Comments

comments