Array shuffle Java
Array shuffle algorithm
Given an array of 2n integers in the following format a1 a2 a3 … an b1 b2 b3 … bn. Rearrange the array as follows a1 b1 a2 b2 a3 b3 … an bn taking into consideration the following restrictions:
1. Arrange the array in place i.e. do not use any additional array
2. Time complexity of the algorithm must be better than O(N2)
Solution
A brute force solution involves two nested loops to rotate the elements in the second half of the array to the left. The first loop runs n times to cover all elements in the second half of the array. The second loop rotates the elements to the left. Note that the start index in the second loop depends on which element we are rotating and the end index depends on how many positions we need to move to the left.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class Shuffle { public static void main(String[] args) { int n = 4; int A[] = {1,3,5,7,2,4,6,8}; //First loop indexed by i goes from 0 to n-1 //Second loop changes its start index depending on //which element we need to rotate to the left side //The number of times the second loop executes is //decreased by one for every element we rotate to //the left side of the array for (int i = 0, q =1, k = n; i < n; i++, k++, q++) { for (int j = k; j > i + q; j--) { int tmp = A[j-1]; A[j-1] = A[j]; A[j] = tmp; } } for (int i = 0; i < 2*n; i++) System.out.println(A[i]); } } |
However this solution has a time complexity of O(n^2). A better solution of time complexity O(nlogn) can be achieved using Divide and Concur technique. Let us take an example
1. Start with the array: a1 a2 a3 a4 b1 b2 b3 b4
2. Split the array into two halves: a1 a2 a3 a4 : b1 b2 b3 b4
2. Exchange elements around the center: exchange a3 a4 with b1 b2 you get: a1 a2 b1 b2 a3 a4 b3 b4
3. Split a1 a2 b1 b2 into a1 a2 : b1 b2 then split a3 a4 b3 b4 into a3 a4 : b3 b4
4. Exchange elements around the center for each subarray you get: a1 b1 a2 b2 and a3 b3 a4 b4
Please note that this solution only handles the case when n = 2^i where i = 0, 1, 2, 3 etc. In our example n = 2^2 = 4 which makes it easy to recursively split the array into two halves. The basic idea behind swapping elements around the center before calling the recursive function is to produce a smaller size problems. A solution with linear time complexity may be achieved if the elements are of specific nature for example if you can calculate the new position of the element using the value of the element itself. This is nothing but a hashing technique.
Code
Here is a sample Java code to do that.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
public class Shuffle { public static void main(String[] args) { int A[] = {1, 3, 5, 7, 2, 4, 6, 8}; Arrange(A, 0, 7); for (int i = 0; i < 8; i++) System.out.println(A[i]); } //l and r are left and right array indexes public static void Arrange(int A[], int l, int r) { //Base case when the array has only one element if (l == r) return; //Array center int c = (l + r)/2; int q = 1 + (l + c)/2; //Swap elements around the center for (int k = 1, i = q; i <= c; i++, k++) { int tmp = A[i]; A[i] = A[c + k]; A[c + k] = tmp; } //Recursively call the function on the left //and right halves of the array Arrange(A, l, c); Arrange(A, c + 1, r); } } |
If you have questions or feedback, please use the comments section below. Thanks for visiting.
About Author
Mohammed Abualrob
Software Engineer @ Cisco