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
Método 1: Fuerza bruta
Una solución de fuerza bruta involucra dos bucles anidados para rotar los elementos en la segunda mitad de la array hacia la izquierda. El primer bucle se ejecuta n veces para cubrir todos los elementos de la segunda mitad de la array. El segundo bucle gira los elementos hacia la izquierda. Tenga en cuenta que el índice de inicio en el segundo bucle depende del elemento que estemos girando y el índice final depende de cuántas posiciones necesitemos mover hacia la izquierda.
A continuación se muestra la implementación de este enfoque:
C++
// C++ Naive program to shuffle an array of size 2n
#include <bits/stdc++.h>
using namespace std;
// function to shuffle an array of size 2n
void shuffleArray(int a[], int n)
{
// Rotate the element to the left
for (int i = 0, q = 1, k = n; i < n; i++, k++, q++)
for (int j = k; j > i + q; j--)
swap(a[j - 1], a[j]);
}
// Driven Program
int main()
{
int a[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
int n = sizeof(a) / sizeof(a[0]);
shuffleArray(a, n / 2);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}
Java
// Java Naive program to shuffle an array of size 2n
import java.util.Arrays;
public class GFG {
// method to shuffle an array of size 2n
static void shuffleArray(int a[], int n)
{
// Rotate the element to the left
for (int i = 0, q = 1, k = n; i < n; i++, k++, q++)
for (int j = k; j > i + q; j--) {
// swap a[j-1], a[j]
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
// Driver Method
public static void main(String[] args)
{
int a[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
shuffleArray(a, a.length / 2);
System.out.println(Arrays.toString(a));
}
}
Python3
# Python3 Naive program to # shuffle an array of size 2n # Function to shuffle an array of size 2n def shuffleArray(a, n): # Rotate the element to the left i, q, k = 0, 1, n while(i < n): j = k while(j > i + q): a[j - 1], a[j] = a[j], a[j - 1] j -= 1 i += 1 k += 1 q += 1 # Driver Code a = [1, 3, 5, 7, 2, 4, 6, 8] n = len(a) shuffleArray(a, int(n / 2)) for i in range(0, n): print(a[i], end = " ") # This code is contributed by Smitha Dinesh Semwal.
C#
// C# Naive program to shuffle an
// array of size 2n
using System;
class GFG {
// method to shuffle an array of size 2n
static void shuffleArray(int[] a, int n)
{
// Rotate the element to the left
for (int i = 0, q = 1, k = n;
i < n; i++, k++, q++)
for (int j = k; j > i + q; j--) {
// swap a[j-1], a[j]
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
// Driver Code
public static void Main()
{
int[] a = { 1, 3, 5, 7, 2, 4, 6, 8 };
shuffleArray(a, a.Length / 2);
for (int i = 0; i < a.Length; i++)
Console.Write(a[i] + " ");
}
}
// This code is contributed
// by ChitraNayal
Javascript
<script>
// Javascript Naive program to shuffle an array of size 2n
// method to shuffle an array of size 2n
function shuffleArray(a,n)
{
// Rotate the element to the left
for (let i = 0, q = 1, k = n; i < n; i++, k++, q++)
for (let j = k; j > i + q; j--) {
// swap a[j-1], a[j]
let temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
// Driver Method
let a=[ 1, 3, 5, 7, 2, 4, 6, 8];
shuffleArray(a, a.length / 2);
document.write(a.join(" "));
//This code is contributed by avanitrachhadiya2155
</script>
Producción
1 2 3 4 5 6 7 8
Complejidad temporal: O(n 2 )
Método 2: (Divide y vencerás):
La idea es utilizar la Técnica Divide y Conquistarás. Divida la array dada por la mitad (digamos arr1[] y arr2[]) e intercambie el segundo medio elemento de arr1[] con el primer medio elemento de arr2[]. Haga esto recursivamente para arr1 y arr2.
Vamos a explicar con la ayuda de un ejemplo.
- Sea la array a1, a2, a3, a4, b1, b2, b3, b4
- Divida la array en dos mitades: a1, a2, a3, a4: b1, b2, b3, b4
- Elemento de intercambio alrededor del centro: intercambiar a3, a4 con b1, b2 correspondientemente.
obtienes: a1, a2, b1, b2, a3, a4, b3, b4 - Divide recursivamente a1, a2, b1, b2 en a1, a2: b1, b2
y luego divide a3, a4, b3, b4 en a3, a4: b3, b4. - Intercambie elementos alrededor del centro para cada subarreglo que obtengamos:
a1, b1, a2, b2 y a3, b3, a4, b4.
Nota: Esta solución solo maneja el caso cuando n = 2 i donde i = 0, 1, 2, etc.
A continuación se muestra la implementación de este enfoque:
C++
// C++ Effective program to shuffle an array of size 2n
#include <bits/stdc++.h>
using namespace std;
// function to shuffle an array of size 2n
void shufleArray(int a[], int f, int l)
{
if (f > l) {
return;
}
// If only 2 element, return
if (l - f == 1)
return;
// finding mid to divide the array
int mid = (f + l) / 2;
// using temp for swapping first half of second array
int temp = mid + 1;
// mmid is use for swapping second half for first array
int mmid = (f + mid) / 2;
// Swapping the element
for (int i = mmid + 1; i <= mid; i++)
swap(a[i], a[temp++]);
// Recursively doing for first half and second half
shufleArray(a, f, mid);
shufleArray(a, mid + 1, l);
}
// Driven Program
int main()
{
int a[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
int n = sizeof(a) / sizeof(a[0]);
shufleArray(a, 0, n - 1);
for (int i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}
Java
// Java Effective program to shuffle an array of size 2n
import java.util.Arrays;
public class GFG {
// method to shuffle an array of size 2n
static void shufleArray(int a[], int f, int l)
{
if (f > l)
return;
// If only 2 element, return
if (l - f == 1)
return;
// finding mid to divide the array
int mid = (f + l) / 2;
// using temp for swapping first half of second array
int temp = mid + 1;
// mmid is use for swapping second half for first array
int mmid = (f + mid) / 2;
// Swapping the element
for (int i = mmid + 1; i <= mid; i++) {
// swap a[i], a[temp++]
int temp1 = a[i];
a[i] = a[temp];
a[temp++] = temp1;
}
// Recursively doing for first half and second half
shufleArray(a, f, mid);
shufleArray(a, mid + 1, l);
}
// Driver Method
public static void main(String[] args)
{
int a[] = { 1, 3, 5, 7, 2, 4, 6, 8 };
shufleArray(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
}
Python3
# Python3 effective program to # shuffle an array of size 2n # Function to shuffle an array of size 2n def shufleArray(a, f, l): if (f > l): return # If only 2 element, return if (l - f == 1): return # Finding mid to divide the array mid = int((f + l) / 2) # Using temp for swapping first # half of the second array temp = mid + 1 # Mid is use for swapping second # half for first array mmid = int((f + mid) / 2) # Swapping the element for i in range(mmid + 1, mid + 1): (a[i], a[temp]) = (a[temp], a[i]) temp += 1 # Recursively doing for first # half and second half shufleArray(a, f, mid) shufleArray(a, mid + 1, l) # Driver Code a = [1, 3, 5, 7, 2, 4, 6, 8] n = len(a) shufleArray(a, 0, n - 1) for i in range(0, n): print(a[i], end = " ") # This code is contributed by Smitha Dinesh Semwal
C#
// C# program program to merge two
// sorted arrays with O(1) extra space.
using System;
// method to shuffle an array of size 2n
public class GFG {
// method to shuffle an array of size 2n
static void shufleArray(int[] a, int f, int l)
{
if (f > l)
return;
// If only 2 element, return
if (l - f == 1)
return;
// finding mid to divide the array
int mid = (f + l) / 2;
// using temp for swapping first half of second array
int temp = mid + 1;
// mmid is use for swapping second half for first array
int mmid = (f + mid) / 2;
// Swapping the element
for (int i = mmid + 1; i <= mid; i++) {
// swap a[i], a[temp++]
int temp1 = a[i];
a[i] = a[temp];
a[temp++] = temp1;
}
// Recursively doing for first half and second half
shufleArray(a, f, mid);
shufleArray(a, mid + 1, l);
}
// Driver Method
public static void Main()
{
int[] a = { 1, 3, 5, 7, 2, 4, 6, 8 };
shufleArray(a, 0, a.Length - 1);
for (int i = 0; i < a.Length; i++)
Console.Write(a[i] + " ");
}
}
/*This code is contributed by 29AjayKumar*/
Javascript
<script>
// Javascript Effective program to
// shuffle an array of size 2n
// method to shuffle an array of size 2n
function shufleArray(a, f, l)
{
if (f > l)
return;
// If only 2 element, return
if (l - f == 1)
return;
// Finding mid to divide the array
let mid = Math.floor((f + l) / 2);
// Using temp for swapping first
// half of second array
let temp = mid + 1;
// mmid is use for swapping second
// half for first array
let mmid = Math.floor((f + mid) / 2);
// Swapping the element
for(let i = mmid + 1; i <= mid; i++)
{
// Swap a[i], a[temp++]
let temp1 = a[i];
a[i] = a[temp];
a[temp++] = temp1;
}
// Recursively doing for first
// half and second half
shufleArray(a, f, mid);
shufleArray(a, mid + 1, l);
}
// Driver Code
let a = [ 1, 3, 5, 7, 2, 4, 6, 8 ];
shufleArray(a, 0, a.length - 1);
document.write(a.join(" "));
// This code is contributed by rag2127
</script>
Producción
1 2 3 4 5 6 7 8
Complejidad de tiempo: O(n log n)
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA