Search⌘ K
Home/
Courses/
Algorithms for Coding Interviews in Java

Solution: Shuffle Integers

This review discusses the solution of shuffling an array of 2n integers without using extra space.

We'll cover the following...

Solution #1

Java
class Shuffle 
{
    public static void shuffleArr(int arr[], int size)  // Swap elements from left to right
    { 
        for (int i = 0, q = 1, k = size; i < size; i++, k++, q++)      
            for (int j = k; j > i + q; j--)  
                Helper.swap(arr, j-1, j); 
    } 
    public static void main( String args[] ) 
    {
        int [] arr = {3, 5, 7, 9, 11, 13};
        shuffleArr(arr, arr.length/2);
        System.out.println( Arrays.toString(arr) );
    }
}

It is safe to assume that for this problem the given array can be divided into two equal halves because the number of elements in the array is 2∗n2*n.

So, the naive (brute-force) approach to this problem is:

  1. Use of two nested loops to transfer the elements in the right half of the array to the left half (lines 5-7).

  2. Run the first loop half the size of array times, i-e, size/2 times, to traverse the elements in the second half of the array (line 5).

  3. Then, transfer the elements of the right half to the left half using the inner loop (lines 6-7).

Note that the start index in the second loop depends on which element we are rotating, and the end index ...