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

0 0 12 minutes read

Given an array arr[] consisting of 2* N elements in the form of { a₁, a₂, …, a_N, b₁, b₂, …, b_{N }}, the task is to shuffle the array to {a₁, b₁, a₂, b₂, …, a_n, b₁} without using extra space.

Examples :

Input: arr[] = { 1, 3, 5, 2, 4, 6 }
Output: 1 2 3 4 5 6
Explanation:
The output contains the elements in the form of { a₁, b₁, a₂, b₂, a₃, b₃ }.

Input: arr[] = {1, 2, 3, -1, -2, -3, }
Output: 1 -1 2 -2 3 -3

Divide and Conquer-based Approach: If the size of an array is a power of 2, then follow the article Shuffle 2n integers in format {a1, b1, a2, b2, a3, b3, ……, an, bn} using divide and conquer technique.
Time Complexity: O(N * log(N))
Auxiliary Space: O(1)

Alternate Approach: The above approach will work for all possible values of N by recursively dividing the array such that the length of both halves is even. Follow the steps below to solve the problem:

Define a recursive function, say shuffle(start, end).
- If array length is divisible by 4, then calculate mid-point of the array, say mid = start + (end – start + 1) / 2.
- Otherwise, mid = start + (end – start + 1) / 2 – 1.
- Calculate mid-points of both subarrays, say mid1 = start + (mid – start)/2, and mid2 = mid + (end – mid + 1) / 2.
- Reverse the subarrays in the ranges [mid1, mid2], [mid1, mid-1], and [mid, mid2 – 1].
- Make recursive calls for subarrays [start, mid – 1] and [mid, end], i.e. shuffle(start, mid – 1) and shuffle(mid, end) respectively.
Finally, print the array.

Illustration:

Consider an array arr[] = {a1, a2, a3, b1, b2, b3}:

Split the array into two halves, both of even length, i.e. a1, a2 : a3, b1, b2, b3.

Reverse the mid of first half to mid of 2nd half, i.e. a1, b1 : a3, a2, b2, b3.

Now, reverse the mid of first half to mid of subarray [0, 5], a1, b1 : a3, a2, b2, b3.

Now reverse mid of subarray [0, 5] to mid of 2nd half, a1, b1 : a2, a3, b2, b3.

Recursively call for arrays {a1, b1}, and {a2, a3, b2, b3}.

Now the array {a2, a3, b2, b3} modifies to {a2, b2, a3, b3} after applying the above operations.

Now the arr[] modifies to {a1, b1, a2, b2, a3, b3}.

Below is the implementation of the above approach:

C

// C program for the above approach
#include <stdio.h>
 
// Function to reverse the array from the
// position 'start' to position 'end'
void reverse(int arr[], int start, int end)
{
 
    // Stores mid of start and end
    int mid = (end - start + 1) / 2;
 
    // Traverse the array in
    // the range [start, end]
    for (int i = 0; i < mid; i++) {
 
        // Stores arr[start + i]
        int temp = arr[start + i];
 
        // Update arr[start + i]
        arr[start + i] = arr[end - i];
 
        // Update arr[end - i]
        arr[end - i] = temp;
    }
    return;
}
 
// Utility function to shuffle the given array
// in the of form {a1, b1, a2, b2, ....an, bn}
void shuffleArrayUtil(int arr[], int start, int end)
{
    int i;
 
    // Stores the length of the array
    int l = end - start + 1;
 
    // If length of the array is 2
    if (l == 2)
        return;
 
    // Stores mid of the { start, end }
    int mid = start + l / 2;
 
    // Divide array into two
    // halves of even length
    if (l % 4) {
 
        // Update mid
        mid -= 1;
    }
 
    // Calculate the mid-points of
    // both halves of the array
    int mid1 = start + (mid - start) / 2;
    int mid2 = mid + (end + 1 - mid) / 2;
 
    // Reverse the subarray made
    // from mid1 to mid2
    reverse(arr, mid1, mid2 - 1);
 
    // Reverse the subarray made
    // from mid1 to mid
    reverse(arr, mid1, mid - 1);
 
    // Reverse the subarray made
    // from mid to mid2
    reverse(arr, mid, mid2 - 1);
 
    // Recursively calls for both
    // the halves of the array
    shuffleArrayUtil(arr, start, mid - 1);
    shuffleArrayUtil(arr, mid, end);
}
 
// Function to shuffle the given array in
// the form of {a1, b1, a2, b2, ....an, bn}
void shuffleArray(int arr[], int N,
                  int start, int end)
{
 
    // Function Call
    shuffleArrayUtil(arr, start, end);
 
    // Print the modified array
    for (int i = 0; i < N; i++)
        printf("%d ", arr[i]);
}
 
// Driver Code
int main()
{
 
    // Given array
    int arr[] = { 1, 3, 5, 2, 4, 6 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Shuffles the given array to the
    // required permutation
    shuffleArray(arr, N, 0, N - 1);
 
    return 0;
}

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to reverse the array from the
// position 'start' to position 'end'
void reverse(int arr[], int start, int end)
{
    // Stores mid of start and end
    int mid = (end - start + 1) / 2;
 
    // Traverse the array in
    // the range [start, end]
    for (int i = 0; i < mid; i++) {
 
        // Stores arr[start + i]
        int temp = arr[start + i];
 
        // Update arr[start + i]
        arr[start + i] = arr[end - i];
 
        // Update arr[end - i]
        arr[end - i] = temp;
    }
    return;
}
 
// Utility function to shuffle the given array
// in the of form {a1, b1, a2, b2, ....an, bn}
void shuffleArrayUtil(int arr[], int start, int end)
{
    int i;
 
    // Stores the length of the array
    int l = end - start + 1;
 
    // If length of the array is 2
    if (l == 2)
        return;
 
    // Stores mid of the { start, end }
    int mid = start + l / 2;
 
    // Divide array into two
    // halves of even length
    if (l % 4) {
 
        // Update mid
        mid -= 1;
    }
 
    // Calculate the mid-points of
    // both halves of the array
    int mid1 = start + (mid - start) / 2;
    int mid2 = mid + (end + 1 - mid) / 2;
 
    // Reverse the subarray made
    // from mid1 to mid2
    reverse(arr, mid1, mid2 - 1);
 
    // Reverse the subarray made
    // from mid1 to mid
    reverse(arr, mid1, mid - 1);
 
    // Reverse the subarray made
    // from mid to mid2
    reverse(arr, mid, mid2 - 1);
 
    // Recursively calls for both
    // the halves of the array
    shuffleArrayUtil(arr, start, mid - 1);
    shuffleArrayUtil(arr, mid, end);
}
 
// Function to shuffle the given array in
// the form of {a1, b1, a2, b2, ....an, bn}
void shuffleArray(int arr[], int N, int start, int end)
{
 
    // Function Call
    shuffleArrayUtil(arr, start, end);
 
    // Print the modified array
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 1, 3, 5, 2, 4, 6 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Shuffles the given array to the
    // required permutation
    shuffleArray(arr, N, 0, N - 1);
 
    return 0;
}
 
// This code is contributed by jainlovely450.

Java

// Java program for the above approach
 
class GFG{
   
// Function to reverse the array from the
// position 'start' to position 'end'
static void reverse(int arr[], int start, int end)
{
 
    // Stores mid of start and end
    int mid = (end - start + 1) / 2;
 
    // Traverse the array in
    // the range [start, end]
    for (int i = 0; i < mid; i++) 
    {
 
        // Stores arr[start + i]
        int temp = arr[start + i];
 
        // Update arr[start + i]
        arr[start + i] = arr[end - i];
 
        // Update arr[end - i]
        arr[end - i] = temp;
    }
    return;
}
 
// Utility function to shuffle the given array
// in the of form {a1, b1, a2, b2, ....an, bn}
static void shuffleArrayUtil(int arr[], int start, int end)
{
    int i;
 
    // Stores the length of the array
    int l = end - start + 1;
 
    // If length of the array is 2
    if (l == 2)
        return;
 
    // Stores mid of the { start, end }
    int mid = start + l / 2;
 
    // Divide array into two
    // halves of even length
    if (l % 4 > 0) 
    {
 
        // Update mid
        mid -= 1;
    }
 
    // Calculate the mid-points of
    // both halves of the array
    int mid1 = start + (mid - start) / 2;
    int mid2 = mid + (end + 1 - mid) / 2;
 
    // Reverse the subarray made
    // from mid1 to mid2
    reverse(arr, mid1, mid2 - 1);
 
    // Reverse the subarray made
    // from mid1 to mid
    reverse(arr, mid1, mid - 1);
 
    // Reverse the subarray made
    // from mid to mid2
    reverse(arr, mid, mid2 - 1);
 
    // Recursively calls for both
    // the halves of the array
    shuffleArrayUtil(arr, start, mid - 1);
    shuffleArrayUtil(arr, mid, end);
}
 
// Function to shuffle the given array in
// the form of {a1, b1, a2, b2, ....an, bn}
static void shuffleArray(int arr[], int N,
                  int start, int end)
{
 
    // Function Call
    shuffleArrayUtil(arr, start, end);
 
    // Print the modified array
    for (int i = 0; i < N; i++)
        System.out.printf("%d ", arr[i]);
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given array
    int arr[] = { 1, 3, 5, 2, 4, 6 };
 
    // Size of the array
    int N = arr.length;
 
    // Shuffles the given array to the
    // required permutation
    shuffleArray(arr, N, 0, N - 1);
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
 
# Function to reverse the array from the
# position 'start' to position 'end'
def reverse(arr, start, end):
 
    # Stores mid of start and end
    mid = (end - start + 1) // 2
 
    # Traverse the array in
    # the range [start, end]
    for i in range(mid):
 
        # Stores arr[start + i]
        temp = arr[start + i]
 
        # Update arr[start + i]
        arr[start + i] = arr[end - i]
 
        # Update arr[end - i]
        arr[end - i] = temp
    return arr
 
# Utility function to shuffle the given array
# in the of form {a1, b1, a2, b2, ....an, bn}
def shuffleArrayUtil(arr, start, end):
    i = 0
 
    # Stores the length of the array
    l = end - start + 1
 
    # If length of the array is 2
    if (l == 2):
        return
 
    # Stores mid of the { start, end }
    mid = start + l // 2
 
    # Divide array into two
    # halves of even length
    if (l % 4):
 
        # Update mid
        mid -= 1
 
    # Calculate the mid-points of
    # both halves of the array
    mid1 = start + (mid - start) // 2
    mid2 = mid + (end + 1 - mid) // 2
 
    # Reverse the subarray made
    # from mid1 to mid2
    arr = reverse(arr, mid1, mid2 - 1)
 
    # Reverse the subarray made
    # from mid1 to mid
    arr = reverse(arr, mid1, mid - 1)
 
    # Reverse the subarray made
    # from mid to mid2
    arr = reverse(arr, mid, mid2 - 1)
 
    # Recursively calls for both
    # the halves of the array
    shuffleArrayUtil(arr, start, mid - 1)
    shuffleArrayUtil(arr, mid, end)
 
# Function to shuffle the given array in
# the form of {a1, b1, a2, b2, ....an, bn}
def shuffleArray(arr, N, start, end):
 
    # Function Call
    shuffleArrayUtil(arr, start, end)
 
    # Print the modified array
    for i in arr:
        print(i, end=" ")
 
# Driver Code
if __name__ == '__main__':
 
    # Given array
    arr = [1, 3, 5, 2, 4, 6]
 
    # Size of the array
    N = len(arr)
 
    # Shuffles the given array to the
    # required permutation
    shuffleArray(arr, N, 0, N - 1)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
public class GFG{
 
// Function to reverse the array from the
// position 'start' to position 'end'
static void reverse(int[] arr, int start, int end)
{
 
    // Stores mid of start and end
    int mid = (end - start + 1) / 2;
 
    // Traverse the array in
    // the range [start, end]
    for (int i = 0; i < mid; i++) 
    {
 
        // Stores arr[start + i]
        int temp = arr[start + i];
 
        // Update arr[start + i]
        arr[start + i] = arr[end - i];
 
        // Update arr[end - i]
        arr[end - i] = temp;
    }
    return;
}
 
// Utility function to shuffle the given array
// in the of form {a1, b1, a2, b2, ....an, bn}
static void shuffleArrayUtil(int[] arr, int start, int end)
{
   
    // Stores the length of the array
    int l = end - start + 1;
 
    // If length of the array is 2
    if (l == 2)
        return;
 
    // Stores mid of the { start, end }
    int mid = start + l / 2;
 
    // Divide array into two
    // halves of even length
    if (l % 4 > 0) 
    {
 
        // Update mid
        mid -= 1;
    }
 
    // Calculate the mid-points of
    // both halves of the array
    int mid1 = start + (mid - start) / 2;
    int mid2 = mid + (end + 1 - mid) / 2;
 
    // Reverse the subarray made
    // from mid1 to mid2
    reverse(arr, mid1, mid2 - 1);
 
    // Reverse the subarray made
    // from mid1 to mid
    reverse(arr, mid1, mid - 1);
 
    // Reverse the subarray made
    // from mid to mid2
    reverse(arr, mid, mid2 - 1);
 
    // Recursively calls for both
    // the halves of the array
    shuffleArrayUtil(arr, start, mid - 1);
    shuffleArrayUtil(arr, mid, end);
}
 
// Function to shuffle the given array in
// the form of {a1, b1, a2, b2, ....an, bn}
static void shuffleArray(int[] arr, int N,
                  int start, int end)
{
 
    // Function Call
    shuffleArrayUtil(arr, start, end);
 
    // Print the modified array
    for (int i = 0; i < N; i++)
        Console.Write(arr[i] + " ");
}
 
// Driver Code
static public void Main ()
{
 
    // Given array
    int[] arr = { 1, 3, 5, 2, 4, 6 };
 
    // Size of the array
    int N = arr.Length;
 
    // Shuffles the given array to the
    // required permutation
    shuffleArray(arr, N, 0, N - 1);
 
}
}
 
// This code is contributed by Dharanendra L V

Javascript

<script>
 
// Javascript program of the above approach
 
// Function to reverse the array from the
// position 'start' to position 'end'
function reverse(arr, start, end)
{
  
    // Stores mid of start and end
    let mid = (end - start + 1) / 2;
  
    // Traverse the array in
    // the range [start, end]
    for (let i = 0; i < mid; i++)
    {
  
        // Stores arr[start + i]
        let temp = arr[start + i];
  
        // Update arr[start + i]
        arr[start + i] = arr[end - i];
  
        // Update arr[end - i]
        arr[end - i] = temp;
    }
    return;
}
  
// Utility function to shuffle the given array
// in the of form {a1, b1, a2, b2, ....an, bn}
function shuffleArrayUtil(arr, start, end)
{
    let i;
  
    // Stores the length of the array
    let l = end - start + 1;
  
    // If length of the array is 2
    if (l == 2)
        return;
  
    // Stores mid of the { start, end }
    let mid = start + l / 2;
  
    // Divide array into two
    // halves of even length
    if (l % 4 > 0)
    {
  
        // Update mid
        mid -= 1;
    }
  
    // Calculate the mid-points of
    // both halves of the array
    let mid1 = start + (mid - start) / 2;
    let mid2 = mid + (end + 1 - mid) / 2;
  
    // Reverse the subarray made
    // from mid1 to mid2
    reverse(arr, mid1, mid2 - 1);
  
    // Reverse the subarray made
    // from mid1 to mid
    reverse(arr, mid1, mid - 1);
  
    // Reverse the subarray made
    // from mid to mid2
    reverse(arr, mid, mid2 - 1);
  
    // Recursively calls for both
    // the halves of the array
    shuffleArrayUtil(arr, start, mid - 1);
    shuffleArrayUtil(arr, mid, end);
}
  
// Function to shuffle the given array in
// the form of {a1, b1, a2, b2, ....an, bn}
function shuffleArray(arr, N,
                  start, end)
{
  
    // Function Call
    shuffleArrayUtil(arr, start, end);
  
    // Print the modified array
    for (let i = 0; i < N; i++)
        document.write(arr[i] + " ");
}
 
    // Driver Code
     
    // Given array
    let arr = [ 1, 3, 5, 2, 4, 6 ];
  
    // Size of the array
    let N = arr.length;
  
    // Shuffles the given array to the
    // required permutation
    shuffleArray(arr, N, 0, N - 1);
  
</script>

Output:

1 2 3 4 5 6

Time Complexity: O(N * log(N))
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!