Shuffle 2n integers as a1-b1-a2-b2-a3-b3-..bn without using extra space

Problem Statement

You are given an array of integers. The problem “Shuffle 2n integers as a1-b1-a2-b2-a3-b3-..bn without using extra space” asks to shuffle all the numbers in the array such that the numbers which are like (x0, x1, x2, x3, y0, y1, y2, y3) will be shuffled like x0, y0, x1, y1, x2, y2, x3, y3 and so on in this manner.

Example

arr[]={1, 3, 5, 7, 2, 4, 6, 8}

1, 2, 3, 4, 5, 6, 7, 8

Explanation

If we compare from first three numbers will be like x0, x1, x2 and next three numbers will be like y0, y1, y2, and it will be arranged in x0, y0, x1, y1, x2, y2.

Algorithm to Shuffle 2n integers as a1-b1-a2-b2-a3-b3-..bn without using extra space

1. Find out the middle index of the array.
2. While middleIndex greater than 0, set count and swappingIndex to middleIndex.
  1. While the count is greater than 0, do the following steps.
    1. Swap the values at swappingIndex and swappingIndex +1(value next to swappingIndex).
    2. Increase the value of swapping index by 1.
  2. Decrease the value of middleIndex by 1.
3. Print the array.

Explanation

We have given an array of integer.  Then we are asked to shuffle all the integer values in a, particularly given manner. We will be traversing only half of the array. And swapping up all the values which come according to the algorithm. First, we are going to check that array should not be null. Ans also, the length of the array should be even. That’s why we check the condition that arrays length should not be odd. If any of the above-mentioned conditions are false, then it will not produce an output.

We will find out the middle index of the array and then check that index’s value and its next index value and simply swap that. For that, we are going to use the nested while loop in the first while loop. Then we are going to traverse it from that current index to 0 and keep decreasing the value of the middle index. Inside the inner while loop, we will store the same value as a current index to swappingIndex and then take the swappingIndex value and its next value and swap it. For the second swap, increase the value of swappingIndex and do swapping for the current swappingIndex and its next index’s value.

For the next traversal, we will decrease the value of the middle index. So that it can take the values from the front of the array. Similarly, count and swappingIndex will be the same as the value of middle Index value which we decreased to traverse the earlier values of the array. After all the swapping we have done, we will be going to print that array, and all the numbers will be shuffled in a given manner.

Code

C++ code to Shuffle 2n integers as a1-b1-a2-b2-a3-b3-..bn without using extra space

#include<iostream>
using namespace std;

void shuffleInt(int arr[], int n)
{
    if (arr == NULL || n % 2 == 1)
        return;

    int middleIndex = (n - 1) / 2;

    while (middleIndex > 0)
    {
        int countIndex = middleIndex, swappingIndex = middleIndex;

        while (countIndex -- > 0)
        {
            int temp = arr[swappingIndex + 1];
            arr[swappingIndex + 1] = arr[swappingIndex];
            arr[swappingIndex] = temp;
            swappingIndex++;
        }
        middleIndex--;
    }
}
int main()
{
    int arr[] = {1, 9, 25, 4, 16, 36};
    int n = sizeof(arr) / sizeof(arr[0]);
    shuffleInt(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i]<<" ";
}

1 4 9 16 25 36

Java code to Shuffle 2n integers as a1-b1-a2-b2-a3-b3-..bn without using extra space

class Shuffle2nIntegers
{
    public static void shuffleInt(int[] arr)
    {

        if (arr == null || arr.length % 2 == 1)
            return;

        int middleIndex = (arr.length - 1) / 2;


        while (middleIndex > 0)
        {
            int countIndex = middleIndex, swappingIndex = middleIndex;

            while (countIndex -- > 0)
            {
                int temp = arr[swappingIndex + 1];
                arr[swappingIndex + 1] = arr[swappingIndex];
                arr[swappingIndex] = temp;
                swappingIndex++;
            }
            middleIndex--;
        }
    }

    public static void main(String[] args)
    {
        int arr[] = {1, 9, 25, 4, 16, 36};
        shuffleInt(arr);
        for (int i = 0; i < arr.length; i++)
            System.out.print( arr[i]+" ");
        System.out.println();
    }
}

1 4 9 16 25 36

Complexity Analysis

Time Complexity

O(n^2) where “n” is the number of elements in the array. As each time we are decreasing the middleIndex by one. But the inner loop runs for middleIndex number of times. You can consider it as simple two nested loops where outer loop runs from i= 0 to n the inner loop runs from i+1 to . Thus the time-complexity is polynomial.

Space Complexity

O(1), because the algorithm is an in-place algorithm. That is all the operations that are being done are replacing the initial array elements’. And any of the new arrays are not made.