Mezclar la array {a1, a2, .. an, b1, b2, .. bn} como {a1, b1, a2, b2, a3, b3, ……, an, bn} sin usar espacio adicional

Dada una array de 2n elementos en el siguiente formato { a1, a2, a3, a4, ….., an, b1, b2, b3, b4, …., bn }. La tarea es barajar la array a {a1, b1, a2, b2, a3, b3, ……, an, bn } sin usar espacio adicional.
Ejemplos: 

Input : arr[] = { 1, 2, 9, 15 }
Output : 1 9 2 15

Input :  arr[] = { 1, 2, 3, 4, 5, 6 }
Output : 1 4 2 5 3 6

Hemos discutido las soluciones O (n ² ) y O (n Log n) de este problema en la publicación a continuación.
Baraja 2n enteros en formato {a1, b1, a2, b2, a3, b3, ……, an, bn} sin usar espacio adicional
Aquí se analiza una nueva solución que funciona en tiempo lineal. Sabemos que el primer y el último número no se mueven de su lugar. Y hacemos un seguimiento del índice del que se selecciona cualquier número y dónde está el índice de destino. Sabemos que, si elegimos ai, tiene que ir al índice 2 * i – 1 y si bi, tiene que ir al índice 2 * i. Podemos verificar desde dónde hemos elegido un número determinado en función del índice de selección si es mayor o menor que n. 
Tendremos que hacer esto 2 * n – 2 veces, suponiendo que n = la mitad de la longitud de la array. 
Obtenemos dos casos, cuando n es par e impar, por lo que inicializamos apropiadamente la variable de inicio. 
Nota: Los índices se consideran 1 basado en una array por simplicidad. 

C++

// C++ program to shuffle an array in O(n) time
// and O(1) extra space
#include <bits/stdc++.h>
using namespace std;

// Shuffles an array of size 2n. Indexes
// are considered starting from 1.
void shufleArray(int a[], int n)
{
    n = n / 2;

    for (int start = n + 1, j = n + 1, done = 0, i;
         done < 2 * n - 2; done++) {
        if (start == j) {
            start--;
            j--;
        }

        i = j > n ? j - n : j;
        j = j > n ? 2 * i : 2 * i - 1;

        swap(a[start], a[j]);
    }
}

// Driven Program
int main()
{
    // The first element is bogus. We have used
    // one based indexing for simplicity.
    int a[] = { -1, 1, 3, 5, 7, 2, 4, 6, 8 };
    int n = sizeof(a) / sizeof(a[0]);

    shufleArray(a, n);

    for (int i = 1; i < n; i++)
        cout << a[i] << " ";

    return 0;
}

Java

// Java program to shuffle an
// array in O(n) time and O(1)
// extra space
import java.io.*;

public class GFG {

    // Shuffles an array of size 2n.
    // Indexes are considered starting
    // from 1.
    static void shufleArray(int[] a, int n)
    {
        int temp;
        n = n / 2;

        for (int start = n + 1, j = n + 1, done = 0, i;
             done < 2 * n - 2; done++) {
            if (start == j) {
                start--;
                j--;
            }

            i = j > n ? j - n : j;
            j = j > n ? 2 * i : 2 * i - 1;
            temp = a[start];
            a[start] = a[j];
            a[j] = temp;
        }
    }

    // Driver code
    static public void main(String[] args)
    {
        // The first element is bogus. We have used
        // one based indexing for simplicity.
        int[] a = { -1, 1, 3, 5, 7, 2, 4, 6, 8 };
        int n = a.length;

        shufleArray(a, n);

        for (int i = 1; i < n; i++)
            System.out.print(a[i] + " ");
    }
}

// This Code is contributed by vt_m.

Python 3

# Python 3 program to shuffle an array 
# in O(n) time and O(1) extra space

# Shuffles an array of size 2n. Indexes
# are considered starting from 1.
def shufleArray(a, n):
    
    n = n // 2

    start = n + 1
    j = n + 1
    for done in range( 2 * n - 2) :
        if (start == j) :
            start -= 1
            j -= 1

        i = j - n if j > n else j
        j = 2 * i if j > n else 2 * i - 1

        a[start], a[j] = a[j], a[start]

# Driver Code
if __name__ == "__main__":
    
    # The first element is bogus. We have used
    # one based indexing for simplicity.
    a = [ -1, 1, 3, 5, 7, 2, 4, 6, 8 ]
    n = len(a)

    shufleArray(a, n)

    for i in range(1, n):
        print(a[i], end = " ")

# This code is contributed 
# by ChitraNayal

C#

// C# program to shuffle an
// array in O(n) time and O(1)
// extra space
using System;

public class GFG {

    // Shuffles an array of size 2n.
    // Indexes are considered starting
    // from 1.
    static void shufleArray(int[] a, int n)
    {
        int temp;
        n = n / 2;

        for (int start = n + 1, j = n + 1, done = 0, i;
             done < 2 * n - 2; done++) {
            if (start == j) {
                start--;
                j--;
            }

            i = j > n ? j - n : j;
            j = j > n ? 2 * i : 2 * i - 1;
            temp = a[start];
            a[start] = a[j];
            a[j] = temp;
        }
    }

    // Driven code
    static public void Main(String[] args)
    {
        // The first element is bogus. We have used
        // one based indexing for simplicity.
        int[] a = { -1, 1, 3, 5, 7, 2, 4, 6, 8 };
        int n = a.Length;

        shufleArray(a, n);

        for (int i = 1; i < n; i++)
            Console.Write(a[i] + " ");
    }
}

// This Code is contributed by vt_m.

PHP

<?php
// PHP program to shuffle an 
// array in O(n) time and O(1)
// extra space

// Shuffles an array of size 2n.
// Indexes are considered starting
// from 1.
function shufleArray($a, $n)
{
    
    $k = intval($n / 2);

    for ($start = $k + 1, 
         $j = $k + 1, $done = 0; 
         $done < 2 * $k - 2; $done++)
    {
        if ($start == $j)
        {
            $start--;
            $j--;
        }

        $i = $j > $k ? $j - $k : $j;
        $j = $j > $k ? 2 * $i : 2 * $i - 1;
        $temp = $a[$start];
        $a[$start] = $a[$j];
        $a[$j] = $temp;

    }
    for ($i = 1; $i < $n; $i++)
                echo $a[$i] . " ";
}

// Driver code

// The first element is bogus. 
// We have used one based 
// indexing for simplicity.
$a = array(-1, 1, 3, 5, 7, 2, 4, 6, 8);
$n = count($a);
shufleArray($a, $n);
    
// This code is contributed by Sam007
?>