Reorganizar números positivos y negativos usando la función de clasificación incorporada

Dada una array de números positivos y negativos, organícelos de manera que todos los enteros negativos aparezcan antes que todos los enteros positivos en la array sin usar ninguna estructura de datos adicional como una tabla hash, arrays, etc. Se debe mantener el orden de aparición.

Ejemplos:

Input :  arr[] = [12, 11, -13, -5, 6, -7, 5, -3, -6]
Output : arr[] = [-13, -5, -7, -3, -6, 12, 11, 6, 5]

Input :  arr[] = [-12, 11, 0, -5, 6, -7, 5, -3, -6]
Output : arr[] =  [-12, -5, -7, -3, -6, 0, 11, 6, 5]

Enfoques anteriores: algunos enfoques ya se han discutido aquí . Se implementaron en el mejor de los casos.

Enfoque 3: Hay otro método para hacerlo. En c++ STL, hay una función incorporada std::sort() . Podemos modificar la función comp() para obtener el resultado deseado. Como tenemos que colocar primero los números negativos y luego los positivos. También tenemos que mantener los ceros (si están presentes) entre números positivos y negativos.

La función comp() en este código reorganiza la array dada en el orden requerido. Aquí en bool comp(int a, int b) , si el entero ‘a’ es del j-ésimo índice y el entero ‘b’ es del i-ésimo índice elementos en el arr[], entonces j>i. La función comp() se llamará de esta manera. Si comp() devuelve verdadero, se realizará el intercambio.

Implementación:

// CPP program to rearrange positive
// and negative integers keeping
// order of elements.
#include <bits/stdc++.h>
 
using namespace std;
 
bool comp(int a, int b)
{
 
// swap not needed
if((a > 0 && b > 0) ||
   (a < 0 && b < 0) ||
   (a > 0 && b < 0 ))
return false;
 
// swap needed
if(a < 0 && b > 0)
return true;
 
// swap not needed
if((a == 0 && b < 0) ||
   (a > 0 && b == 0))
return false;
 
// swap needed
if((a == 0 && b > 0) ||
   (a < 0 && b == 0))
return true;
 
}
 
void rearrange(int arr[], int n)
{
    sort(arr, arr + n, comp);
}
 
// Driver code
int main()
{
    int arr[] = { -12, 11, -13, -5,
                  6, -7, 5, -3, -6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrange(arr, n);
    for (int i = 0; i < n; i++)
        cout << " " << arr[i];
 
    return 0;
}

 -12 -13 -5 -7 -3 -6 11 6 5

La complejidad del tiempo es la misma que la clasificación, es decir , O(n log n) . Como estamos usando la función de clasificación estándar. Pero es realmente más rápido porque la función de clasificación incorporada usa introsort .
Espacio Auxiliar: O(1), ya que no se utiliza espacio extra

Enfoque 4: Hay otro método más para resolver este problema. Atravesamos recursivamente la array cortándola en dos mitades ( array[start..start] & array[(start + 1)..end] , y seguimos dividiendo la array hasta llegar al último elemento. Luego comenzamos a fusionarla de nuevo La idea es, en cualquier momento, mantener la array en la secuencia adecuada de enteros negativos y positivos. 

La lógica de fusión sería:

1. Si la array[comienzo] es negativa, combine el resto de la array tal como está para que se mantenga el orden de los números negativos. La razón de esto es que dado que estamos retrocediendo desde las llamadas recursivas, comenzamos a movernos de derecha a izquierda a través de la array, por lo tanto, naturalmente, mantenemos la secuencia original.
2.  Si el array[start] es positivo, combine el resto del array, pero, después de girar a la derecha, la mitad del array[(start + 1)..end] . La idea de la rotación es fusionar la array para que la array positiva [inicio] siempre se fusione con los elementos positivos. Pero lo único aquí es que la array fusionada tendrá todos los elementos positivos a la izquierda y los elementos negativos a la derecha. Así que invertimos la secuencia en cada recursión para recuperar la secuencia original de elementos negativos y luego los elementos positivos posteriormente.
   Se puede observar que invertimos la array mientras se fusiona con un primer elemento positivo en cada recursión, por lo que la secuencia de elementos positivos, aunque viene después de los elementos negativos, está en orden inverso. Entonces, como paso final, invertimos solo la mitad positiva de la array final y, posteriormente, obtenemos la secuencia deseada.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of
// the above approach
#include <iostream>
 
void printArray(int array[], int length)
{
    std::cout << "[";
     
    for(int i = 0; i < length; i++)
    {
        std::cout << array[i];
         
        if(i < (length - 1))
            std::cout << ", ";
        else
            std::cout << "]" << std::endl;
    }
}
 
void reverse(int array[], int start, int end)
{
    while(start < end)
    {
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
        start++;
        end--;
    }
}
 
// Rearrange the array with all negative integers
// on left and positive integers on right
// use recursion to split the array with first element
// as one half and the rest array as another and then
// merge it with head of the array in each step 
void rearrange(int array[], int start, int end)
{
    // exit condition
    if(start == end)
        return;
     
    // rearrange the array except the first
    // element in each recursive call
    rearrange(array, (start + 1), end);
     
    // If the first element of the array is positive,
    // then right-rotate the array by one place first
    // and then reverse the merged array.
    if(array[start] >= 0)
    {
        reverse(array, (start + 1), end);
        reverse(array, start, end);
    }
}
 
// Driver code
int main()
{
    int array[] = {-12, -11, -13, -5, -6, 7, 5, 3, 6};
    int length = (sizeof(array) / sizeof(array[0]));
    int countNegative = 0;
     
    for(int i = 0; i < length; i++)
    {
        if(array[i] < 0)
            countNegative++;
    }
     
    std::cout << "array: ";
    printArray(array, length);
    rearrange(array, 0, (length - 1));
     
    reverse(array, countNegative, (length - 1));
     
    std::cout << "rearranged array: ";
    printArray(array, length);
    return 0;
}

// Java program to implement the
// above approach
import java.io.*;
class GFG{
 
static void printArray(int[] array, int length)
{
  System.out.print("[");
 
  for (int i = 0; i < length; i++)
  {
    System.out.print(array[i]);
 
    if (i < (length - 1))
      System.out.print(",");
    else
      System.out.print("]\n");
  }
}
 
static void reverse(int[] array,
                    int start,
                    int end)
{
  while (start < end)
  {
    int temp = array[start];
    array[start] = array[end];
    array[end] = temp;
    start++;
    end--;
  }
}
 
// Rearrange the array with
// all negative integers on left
// and positive integers on right
// use recursion to split the
// array with first element
// as one half and the rest
// array as another and then
// merge it with head of
// the array in each step
static void rearrange(int[] array,
                      int start,
                      int end)
{
  // exit condition
  if (start == end)
    return;
 
  // rearrange the array
  // except the first element
  // in each recursive call
  rearrange(array,
            (start + 1), end);
 
  // If the first element of
  // the array is positive,
  // then right-rotate the
  // array by one place first
  // and then reverse the merged array.
  if (array[start] >= 0)
  {
    reverse(array,
            (start + 1), end);
    reverse(array,
            start, end);
  }
}
 
// Driver code
public static void main(String[] args)
{
 
  int[] array = {-12, -11, -13,
                 -5, -6, 7, 5, 3, 6};
  int length = array.length;
  int countNegative = 0;
 
  for (int i = 0; i < length; i++)
  {
    if (array[i] < 0)
      countNegative++;
  }
 
  System.out.print("array: ");
  printArray(array, length);
  rearrange(array, 0,
           (length - 1));
  reverse(array, countNegative,
         (length - 1));
  System.out.print("rearranged array: ");
  printArray(array, length);
}
}
 
// This code is contributed by Chitranayal

# Python3 implementation of the above approach
def printArray(array, length):
    print("[", end = "")
 
    for i in range(length):
        print(array[i], end = "")
 
        if(i < (length - 1)):
            print(",", end = " ")
        else:
            print("]")
 
def reverse(array, start, end):
    while(start < end):
        temp = array[start]
        array[start] = array[end]
        array[end] = temp
        start += 1
        end -= 1
 
# Rearrange the array with all negative integers
# on left and positive integers on right
# use recursion to split the array with first element
# as one half and the rest array as another and then
# merge it with head of the array in each step
def rearrange(array, start, end):
     
    # exit condition
    if(start == end):
        return
 
    # rearrange the array except the first
    # element in each recursive call
    rearrange(array, (start + 1), end)
 
    # If the first element of the array is positive,
    # then right-rotate the array by one place first
    # and then reverse the merged array.
    if(array[start] >= 0):
        reverse(array, (start + 1), end)
        reverse(array, start, end)
 
# Driver code
if __name__ == '__main__':
    array = [-12, -11, -13, -5, -6, 7, 5, 3, 6]
    length = len(array)
    countNegative = 0
 
    for i in range(length):
        if(array[i] < 0):
            countNegative += 1
 
    print("array: ", end = "")
    printArray(array, length)
    rearrange(array, 0, (length - 1))
 
    reverse(array, countNegative, (length - 1))
 
    print("rearranged array: ", end = "")
    printArray(array, length)
 
# This code is contributed by mohit kumar 29

// C# implementation of
// the above approach
using System;
class GFG{
 
static void printArray(int []array,
                       int length)
{
  Console.Write("[");
 
  for(int i = 0; i < length; i++)
  {
    Console.Write(array[i]);
 
    if(i < (length - 1))
      Console.Write(",");
    else
      Console.Write("]\n");
  }
}
  
static void reverse(int []array,
                    int start, int end)
{
  while(start < end)
  {
    int temp = array[start];
    array[start] = array[end];
    array[end] = temp;
    start++;
    end--;
  }
}
  
// Rearrange the array with
// all negative integers on left
// and positive integers on right
// use recursion to split the
// array with first element
// as one half and the rest
// array as another and then
// merge it with head of
// the array in each step 
static void rearrange(int []array,
                      int start, int end)
{
  // exit condition
  if(start == end)
    return;
 
  // rearrange the array
  // except the first element
  // in each recursive call
  rearrange(array,
            (start + 1), end);
 
  // If the first element of
  // the array is positive,
  // then right-rotate the
  // array by one place first
  // and then reverse the merged array.
  if(array[start] >= 0)
  {
    reverse(array, (start + 1), end);
    reverse(array, start, end);
  }
}
      
// Driver code
public static void Main(string[] args)
{
 
  int []array = {-12, -11, -13,
                 -5, -6, 7, 5, 3, 6};
  int length = array.Length;
  int countNegative = 0;
 
  for(int i = 0; i < length; i++)
  {
    if(array[i] < 0)
      countNegative++;
  }
   
  Console.Write("array: ");
  printArray(array, length);
  rearrange(array, 0, (length - 1));
  reverse(array, countNegative, (length - 1));
  Console.Write("rearranged array: ");
  printArray(array, length);
}
}
 
// This code is contributed by Rutvik_56

<script>
// Javascript program to implement the
// above approach
function printArray(array, Length)
{
    document.write("[");
  
  for (let i = 0; i < Length; i++)
  {
    document.write(array[i]);
  
    if (i < (Length - 1))
      document.write(",");
    else
      document.write("]<br>");
  }
}
 
function reverse(array,start,end)
{
    while (start < end)
  {
    let temp = array[start];
    array[start] = array[end];
    array[end] = temp;
    start++;
    end--;
  }
}
 
// Rearrange the array with
// all negative integers on left
// and positive integers on right
// use recursion to split the
// array with first element
// as one half and the rest
// array as another and then
// merge it with head of
// the array in each step
function rearrange(array,start,end)
{
 
    // exit condition
  if (start == end)
    return;
  
  // rearrange the array
  // except the first element
  // in each recursive call
  rearrange(array, (start + 1), end);
  
  // If the first element of
  // the array is positive,
  // then right-rotate the
  // array by one place first
  // and then reverse the merged array.
  if (array[start] >= 0)
  {
    reverse(array, (start + 1), end);
    reverse(array, start, end);
  }
}
 
// Driver code
let array = [-12, -11, -13,
                 -5, -6, 7, 5, 3, 6];
let length = array.length;
let countNegative = 0;
for (let i = 0; i < length; i++)
  {
    if (array[i] < 0)
      countNegative++;
  }
  
  document.write("array: ");
  printArray(array, length);
  rearrange(array, 0,
           (length - 1));
  reverse(array, countNegative,
         (length - 1));
  document.write("rearranged array: ");
  printArray(array, length);
     
    // This code is contributed by rag2127.
</script>

array: [-12, -11, -13, -5, -6, 7, 5, 3, 6]
rearranged array: [-12, -11, -13, -5, -6, 7, 5, 3, 6]

Complejidad de tiempo: O(N ² )
Espacio auxiliar: O(N ² ) , ya que se usa pila implícita debido a llamadas recursivas

Este artículo es una contribución de abhijeet kaurav . 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.