Segregar números pares e impares | conjunto 2 – Part 1

Dada una array arr[] de tamaño N , la tarea es segregar números pares e impares. Imprime primero todos los números pares y luego los impares.

Ejemplos: 

Entrada: arr[] = {8, 22, 65, 70, 33, 60, 2, 34, 43, 21} 
Salida: {8, 22, 70, 60, 2, 34, 65, 33, 43, 21} 

Entrada: arr[] = {18, 52, 37, 70, 3, 63, 2, 34} 
Salida: {18, 52, 70, 2, 34, 37, 3, 63} 

Enfoque lineal: este problema puede verse como una variación del problema de la bandera nacional holandesa . Consulte la publicación anterior para conocer todos los enfoques lineales para resolver el problema.

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)

Enfoque usando la función stable_partition() : El algoritmo stable_partition() organiza la secuencia definida por el inicio y el final de tal manera que todos los elementos para los cuales el predicado, especificado por la función de predicado definida por el usuario, devuelve True , precede a aquellos para los que la función devuelve False . La partición es estable. Por lo tanto, se conserva el orden relativo de la secuencia.

Sintaxis: 

plantilla 
BiIter stable_partition(BiIter start, BiIter end, UnPred pfn) 

Parámetros:  

inicio: el rango de elementos para reordenar 
fin: el rango de elementos para reordenar 
pfn: Objeto de función de predicado definido por el usuario que define la condición que debe cumplirse si se va a clasificar un elemento. 
Un predicado toma un único argumento y devuelve True o False . 
Valor devuelto: Devuelve un iterador al principio de los elementos para los que el predicado es falso. 

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to segregate
// odd and even numbers
void segregate(vector<int> arr)
{
 
    // Using stable partition
    // with lambda expression
    stable_partition(arr.begin(),
                     arr.end(),
                     [](int a) {
                         return a % 2 == 0;
                     });
 
    // Print array after partition
    for (int num : arr)
        cout << num << " ";
}
 
// Driver Code
int main()
{
    // Given array arr[]
    vector<int> arr = { 18, 52, 37, 70,
                        3, 63, 2, 34 };
 
    // Function Call
    segregate(arr);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG{
   
static int[] stable_partition(int arr[])
{
  // Initialize left and
  // right indexes
  int left = 0,
      right = arr.length - 1;
   
  while (left < right)
  {
    // Increment left index while
    // we see 0 at left
    while (arr[left] % 2 == 0 &&
           left < right)
      left++;
 
    // Decrement right index while
    // we see 1 at right
    while (arr[right] % 2 == 1 &&
           left < right)
      right--;
 
    if (left < right)
    {
      // Swap arr[left] and
      // arr[right]
      int temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    }
  }
  return arr;
}
 
// Function to segregate
// odd and even numbers
static void segregate(int[] arr)
{
  // Using stable partition
  // with lambda expression
  int []ans = stable_partition(arr);
 
  // Print array after partition
  for (int num : ans)
    System.out.print(num + " ");
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array arr[]
  int[] arr = {18, 52, 37, 70,
               3, 63, 2, 34};
 
  // Function Call
  segregate(arr);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to implement
# the above approach
 
# Function to segregate
# odd and even numbers
def segregate(arr):
     
    # Using stable partition
    # with lambda expression
    odd = []
    even = []
     
    for x in arr:
        if (x % 2 == 0):
            even.append(x)
        else:
            odd.append(x)
             
    for x in even:
        print(x, end = " ")
    for x in odd:
        print(x, end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 18, 52, 37, 70, 3, 63, 2, 34 ]
 
    # Function Call
    segregate(arr)
 
# This code is contributed by SURENDRA_GANGWAR

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
   
static void stable_partition(int []arr)
{
  // Initialize left and
  // right indexes
  List<int> odd = new List<int>();
  List<int> even = new List<int>();
 
  foreach(int i in arr)
  {
    if(i % 2 == 1)
      odd.Add(i);
    else
      even.Add(i);
  }
   
  foreach(int i in even)
    Console.Write(i +" ");
   
  foreach(int i in odd)
    Console.Write(i +" ");
}
 
// Function to segregate
// odd and even numbers
static void segregate(int[] arr)
{
  // Using stable partition
  // with lambda expression
  stable_partition(arr);
 
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array []arr
  int[] arr = {18, 52, 37, 70,
               3, 63, 2, 34};
 
  // Function Call
  segregate(arr);
}
}
 
// This code is contributed by 29AjayKumar

18 52 70 2 34 37 3 63 

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)