Se le ha dado una array y tiene que hacer un programa para convertir esa array de modo que los elementos positivos se presenten en los lugares pares de la array y los elementos negativos se produzcan en los lugares impares de la array. Tenemos que hacerlo en el lugar.
Puede haber un número desigual de valores positivos y negativos y los valores adicionales deben dejarse como están.
Ejemplos:
Input : arr[] = {1, -3, 5, 6, -3, 6, 7, -4, 9, 10}
Output : arr[] = {1, -3, 5, -3, 6, 6, 7, -4, 9, 10}
Input : arr[] = {-1, 3, -5, 6, 3, 6, -7, -4, -9, 10}
Output : arr[] = {3, -1, 6, -5, 3, -7, 6, -4, 10, -9}
La idea es utilizar el proceso de partición de Quick Sort de Hoare .
Tomamos dos punteros positivo y negativo. Establecemos el puntero positivo al comienzo de la array y el puntero negativo en la primera posición de la array.
Movemos el puntero positivo dos pasos hacia adelante hasta que encuentre un elemento negativo. De manera similar, movemos el puntero negativo hacia adelante dos lugares hasta que encuentre un valor positivo en su posición.
Si los punteros positivo y negativo están en la array, intercambiaremos los valores en estos índices; de lo contrario, dejaremos de ejecutar el proceso.
Implementación:
C++
// C++ program to rearrange positive and negative
// numbers
#include <bits/stdc++.h>
using namespace std;
void rearrange(int a[], int size)
{
int positive = 0, negative = 1;
while (true) {
/* Move forward the positive pointer till
negative number number not encountered */
while (positive < size && a[positive] >= 0)
positive += 2;
/* Move forward the negative pointer till
positive number number not encountered */
while (negative < size && a[negative] <= 0)
negative += 2;
// Swap array elements to fix their position.
if (positive < size && negative < size)
swap(a[positive], a[negative]);
/* Break from the while loop when any index
exceeds the size of the array */
else
break;
}
}
// Driver code
int main()
{
int arr[] = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 };
int n = (sizeof(arr) / sizeof(arr[0]));
rearrange(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// Java program to rearrange positive
// and negative numbers
import java.io.*;
class GFG {
static void rearrange(int a[], int size)
{
int positive = 0, negative = 1, temp;
while (true) {
/* Move forward the positive pointer till
negative number number not encountered */
while (positive < size && a[positive] >= 0)
positive += 2;
/* Move forward the negative pointer till
positive number number not encountered */
while (negative < size && a[negative] <= 0)
negative += 2;
// Swap array elements to fix their position.
if (positive < size && negative < size) {
temp = a[positive];
a[positive] = a[negative];
a[negative] = temp;
}
/* Break from the while loop when any index
exceeds the size of the array */
else
break;
}
}
// Driver code
public static void main(String args[]) {
int arr[] = {1, -3, 5, 6, -3, 6, 7, -4, 9, 10};
int n = arr.length;
rearrange(arr, n);
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Python 3 program to rearrange # positive and negative numbers def rearrange(a, size) : positive = 0 negative = 1 while (True) : # Move forward the positive # pointer till negative number # number not encountered while (positive < size and a[positive] >= 0) : positive = positive + 2 # Move forward the negative # pointer till positive number # number not encountered while (negative < size and a[negative] <= 0) : negative = negative + 2 # Swap array elements to fix # their position. if (positive < size and negative < size) : temp = a[positive] a[positive] = a[negative] a[negative] = temp # Break from the while loop when # any index exceeds the size of # the array else : break # Driver code arr =[ 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 ] n = len(arr) rearrange(arr, n) for i in range(0, n) : print(arr[i], end = " ") # This code is contributed by Nikita Tiwari.
C#
// C# program to rearrange positive
// and negative numbers
using System;
class GFG {
// Function to rearrange
static void rearrange(int []a, int size)
{
int positive = 0, negative = 1, temp;
while (true) {
// Move forward the positive pointer till
// negative number number not encountered
while (positive < size && a[positive] >= 0)
positive += 2;
// Move forward the negative pointer till
// positive number number not encountered
while (negative < size && a[negative] <= 0)
negative += 2;
// Swap array elements to fix their position.
if (positive < size && negative < size) {
temp = a[positive];
a[positive] = a[negative];
a[negative] = temp;
}
// Break from the while loop when any
// index exceeds the size of the array
else
break;
}
}
// Driver Code
public static void Main(String []args) {
int []arr = {1, -3, 5, 6, -3, 6, 7, -4, 9, 10};
int n = arr.Length;
rearrange(arr, n);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to rearrange positive
// and negative numbers
function rearrange(&$a, $size)
{
$positive = 0;
$negative = 1;
while (true)
{
/* Move forward the positive
pointer till negative number
number not encountered */
while ($positive < $size &&
$a[$positive] >= 0)
$positive += 2;
/* Move forward the negative
pointer till positive number
number not encountered */
while ($negative < $size &&
$a[$negative] <= 0)
$negative += 2;
// Swap array elements to fix
// their position.
if ($positive < $size &&
$negative < $size)
{
$temp = $a[$positive];
$a[$positive] = $a[$negative];
$a[$negative] = $temp;
}
/* Break from the while loop
when any index exceeds the
size of the array */
else
break;
}
}
// Driver code
$arr = array( 1, -3, 5, 6, -3,
6, 7, -4, 9, 10 );
$n = sizeof($arr);
rearrange($arr, $n);
for ($i = 0; $i < $n; $i++)
echo $arr[$i] ." ";
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// Javascript program to rearrange positive
// and negative numbers
function rearrange(a, size)
{
let positive = 0;
let negative = 1;
let temp;
while (true)
{
// Move forward the positive
// pointer till negative number
// number not encountered
while (positive < size && a[positive] >= 0)
positive += 2;
// Move forward the negative pointer
// till positive number number not encountered
while (negative < size && a[negative] <= 0)
negative += 2;
// Swap array elements to fix their position.
if (positive < size && negative < size)
{
temp = a[positive];
a[positive] = a[negative];
a[negative] = temp;
}
// Break from the while loop when any index
// exceeds the size of the array
else
break;
}
}
// Driver code
let arr = [ 1, -3, 5, 6, -3,
6, 7, -4, 9, 10 ];
let n = arr.length;
rearrange(arr, n);
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by sravan kumar G
</script>
1 -3 5 -3 6 6 7 -4 9 10
Complejidad de Tiempo: O(n 2 ),
Espacio Auxiliar: O(1)
Expliquemos el funcionamiento del código en el primer ejemplo
arr[] = {1, -3, 5, 6, -3, 6, 7, -4, 9, 10}
Declaramos dos variables positivo y negativo puntos positivos a cero posición y puntos negativos a la primera posición
positivo = 0 negativo = 1
En la primera iteración, el positivo se moverá 4 lugares a la quinta posición ya que a[4] es menor que cero y positivo = 4.
El negativo se moverá 2 lugares y apuntará a la cuarta posición como a[3]>0
, intercambiaremos valores de posición positivos y negativos, ya que son menores que el tamaño de la array.
Después de la primera iteración, la array se convierte en arr[] = {1, -3, 5, -3, 6, 6, 7, -4, 9, 10}
Ahora puntos positivos en la cuarta posición y puntos negativos en la tercera posición
En la segunda iteración, el valor positivo se moverá 6 lugares y su valor será
mayor que el tamaño de la array.
El puntero negativo avanzará dos pasos y apuntará a la quinta posición.
A medida que el valor del puntero positivo sea mayor que el tamaño de la array
, no realizaremos ninguna operación de intercambio y saldremos del bucle while.
El resultado final será
arr[] = {1, -3, 5, -3, 6, 6, 7, -4, 9, 10}
Un ejemplo donde no se mantiene el orden relativo:
{ -1, -2, -3, -4, -5, 6, 7, 8 };
Otro enfoque: –
La idea es encontrar un elemento positivo/negativo que esté en el lugar incorrecto (es decir, positivo en el lugar impar y negativo en el lugar par) y luego encontrar el elemento de signo opuesto que también esté en la posición incorrecta en la array restante y luego intercambie estos dos elementos.
Aquí está la implementación de la idea anterior.
C++
// C++ program to rearrange positive
// and negative numbers
#include<iostream>
using namespace std;
// Swap function
void swap(int* a, int i , int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
return ;
}
// Print array function
void printArray(int* a, int n)
{
for(int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
return ;
}
// Driver code
int main()
{
int arr[] = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 };
int n = sizeof(arr)/sizeof(arr[0]);
//before modification
printArray(arr, n);
for(int i = 0; i < n; i++)
{
if(arr[i] >= 0 && i % 2 == 1)
{
// out of order positive element
for(int j = i + 1; j < n; j++)
{
if(arr[j] < 0 && j % 2 == 0)
{
// find out of order negative
// element in remaining array
swap(arr, i, j);
break ;
}
}
}
else if(arr[i] < 0 && i % 2 == 0)
{
// out of order negative element
for(int j = i + 1; j < n; j++)
{
if(arr[j] >= 0 && j % 2 == 1)
{
// find out of order positive
// element in remaining array
swap(arr, i, j);
break;
}
}
}
}
//after modification
printArray(arr, n);
return 0;
}
// This code is contributed by AnitAggarwal
Java
// Java program to rearrange positive
// and negative numbers
import java.io.*;
import java.util.*;
class GFG
{
// Swap function
static void swap(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// Print array function
static void printArray(int[] a, int n)
{
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
System.out.println();
}
// Driver code
public static void main(String args[])
{
int[] arr = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 };
int n = arr.length;
//before modification
printArray(arr, n);
for (int i = 0; i < n; i++)
{
if (arr[i] >= 0 && i % 2 == 1)
{
// out of order positive element
for (int j = i + 1; j < n; j++)
{
if (arr[j] < 0 && j % 2 == 0)
{
// find out of order negative
// element in remaining array
swap(arr, i, j);
break ;
}
}
}
else if (arr[i] < 0 && i % 2 == 0)
{
// out of order negative element
for (int j = i + 1; j < n; j++)
{
if (arr[j] >= 0 && j % 2 == 1)
{
// find out of order positive
// element in remaining array
swap(arr, i, j);
break;
}
}
}
}
//after modification
printArray(arr, n);
}
}
// This code is contributed by rachana soma
Python3
# Python3 program to rearrange positive # and negative numbers # Print array function def printArray(a, n): for i in a: print(i, end = " ") print() # Driver code arr = [1, -3, 5, 6, -3, 6, 7, -4, 9, 10] n = len(arr) # before modification printArray(arr, n) for i in range(n): if(arr[i] >= 0 and i % 2 == 1): # out of order positive element for j in range(i + 1, n): if(arr[j] < 0 and j % 2 == 0): # find out of order negative # element in remaining array arr[i], arr[j] = arr[j], arr[i] break elif (arr[i] < 0 and i % 2 == 0): # out of order negative element for j in range(i + 1, n): if(arr[j] >= 0 and j % 2 == 1): # find out of order positive # element in remaining array arr[i], arr[j] = arr[j], arr[i] break # after modification printArray(arr, n); # This code is contributed # by mohit kumar
C#
// C# program to rearrange positive
// and negative numbers
using System;
class GFG
{
// Swap function
static void swap(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// Print array function
static void printArray(int[] a, int n)
{
for (int i = 0; i < n; i++)
Console.Write(a[i] + " ");
Console.WriteLine();
}
// Driver code
public static void Main()
{
int[] arr = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 };
int n = arr.Length;
//before modification
printArray(arr, n);
for (int i = 0; i < n; i++)
{
if (arr[i] >= 0 && i % 2 == 1)
{
// out of order positive element
for (int j = i + 1; j < n; j++)
{
if (arr[j] < 0 && j % 2 == 0)
{
// find out of order negative
// element in remaining array
swap(arr, i, j);
break ;
}
}
}
else if (arr[i] < 0 && i % 2 == 0)
{
// out of order negative element
for (int j = i + 1; j < n; j++)
{
if (arr[j] >= 0 && j % 2 == 1)
{
// find out of order positive
// element in remaining array
swap(arr, i, j);
break;
}
}
}
}
// after modification
printArray(arr, n);
}
}
// This code is contributed by Akanksha Rai
Javascript
<script>
// Javascript program to rearrange positive
// and negative numbers
// Swap function
function swap(a,i,j)
{
let temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// Print array function
function printArray(a,n)
{
for (let i = 0; i < n; i++)
document.write(a[i] + " ");
document.write("<br>");
}
// Driver code
let arr=[1, -3, 5, 6, -3, 6, 7, -4, 9, 10];
let n = arr.length;
//before modification
printArray(arr, n);
for (let i = 0; i < n; i++)
{
if (arr[i] >= 0 && i % 2 == 1)
{
// out of order positive element
for (let j = i + 1; j < n; j++)
{
if (arr[j] < 0 && j % 2 == 0)
{
// find out of order negative
// element in remaining array
swap(arr, i, j);
break ;
}
}
}
else if (arr[i] < 0 && i % 2 == 0)
{
// out of order negative element
for (let j = i + 1; j < n; j++)
{
if (arr[j] >= 0 && j % 2 == 1)
{
// find out of order positive
// element in remaining array
swap(arr, i, j);
break;
}
}
}
}
//after modification
printArray(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
1 -3 5 6 -3 6 7 -4 9 10 1 -3 5 -3 6 6 7 -4 9 10
Complejidad de Tiempo: O(n 2 ),
Espacio Auxiliar: O(1)
Este artículo es una contribución de Ashish Madaan . 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