Dada una array A[], escriba una función que segregue números pares e impares. Las funciones deben poner todos los números pares primero y luego los números impares.
Ejemplo:
Input = {12, 34, 45, 9, 8, 90, 3}
Output = {12, 34, 8, 90, 45, 9, 3}
En la salida, se puede cambiar el orden de los números, es decir, en el ejemplo anterior, 34 puede aparecer antes que 12 y 3 puede aparecer antes que 9.
El problema es muy similar a nuestra publicación anterior Segregar 0 y 1 en una array , y ambos problemas son una variación del famoso problema de la bandera nacional holandesa .
Algorithm: segregateEvenOdd()
1) Initialize two index variables left and right:
left = 0, right = size -1
2) Keep incrementing left index until we see an even number.
3) Keep decrementing right index until we see an odd number.
4) If left < right then swap arr[left] and arr[right]
Implementación:
C++
// C++ program to segregate even and odd elements of array
#include <iostream>
using namespace std;
/* Function to swap *a and *b */
void swap(int *a, int *b);
void segregateEvenOdd(int arr[], int size)
{
/* Initialize left and right indexes */
int left = 0, right = size-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]*/
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
}
/* UTILITY FUNCTIONS */
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
/* Driver code */
int main()
{
int arr[] = {12, 34, 45, 9, 8, 90, 3};
int arr_size = sizeof(arr)/sizeof(arr[0]);
int i = 0;
segregateEvenOdd(arr, arr_size);
cout <<"Array after segregation ";
for (i = 0; i < arr_size; i++)
cout << arr[i] << " ";
return 0;
}
// This code is contributed by shubhamsingh10
C
// C program to segregate even and odd elements of array
#include<stdio.h>
/* Function to swap *a and *b */
void swap(int *a, int *b);
void segregateEvenOdd(int arr[], int size)
{
/* Initialize left and right indexes */
int left = 0, right = size-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]*/
swap(&arr[left], &arr[right]);
left++;
right--;
}
}
}
/* UTILITY FUNCTIONS */
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
/* driver program to test */
int main()
{
int arr[] = {12, 34, 45, 9, 8, 90, 3};
int arr_size = sizeof(arr)/sizeof(arr[0]);
int i = 0;
segregateEvenOdd(arr, arr_size);
printf("Array after segregation ");
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
return 0;
}
Java
// Java program to segregate even and odd elements of array
import java.io.*;
class SegregateOddEven
{
static void segregateEvenOdd(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--;
}
}
}
/* Driver program to test above functions */
public static void main (String[] args)
{
int arr[] = {12, 34, 45, 9, 8, 90, 3};
segregateEvenOdd(arr);
System.out.print("Array after segregation ");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i]+" ");
}
}
/*This code is contributed by Devesh Agrawal*/
Python
# Python program to segregate even and odd elements of array
def segregateEvenOdd(arr):
# Initialize left and right indexes
left,right = 0,len(arr)-1
while left < right:
# Increment left index while we see 0 at left
while (arr[left]%2==0 and left < right):
left += 1
# Decrement right index while we see 1 at right
while (arr[right]%2 == 1 and left < right):
right -= 1
if (left < right):
# Swap arr[left] and arr[right]*/
arr[left],arr[right] = arr[right],arr[left]
left += 1
right = right-1
# Driver function to test above function
arr = [12, 34, 45, 9, 8, 90, 3]
segregateEvenOdd(arr)
print ("Array after segregation "),
for i in range(0,len(arr)):
print arr[i],
# This code is contributed by Devesh Agrawal
C#
// C# program to segregate even
// and odd elements of array
using System;
class GFG
{
static void segregateEvenOdd(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--;
}
}
}
/* Driver program to test above functions */
public static void Main ()
{
int []arr = {12, 34, 45, 9, 8, 90, 3};
segregateEvenOdd(arr);
Console.Write("Array after segregation ");
for (int i = 0; i < arr.Length; i++)
Console.Write(arr[i]+" ");
}
}
//This code is contributed by Sam007
PHP
<?php
// PHP program to segregate even and
// odd elements of array
function segregateEvenOdd(&$arr, $size)
{
// Initialize left and right indexes
$left = 0;
$right = $size-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]
swap($arr[$left], $arr[$right]);
$left++;
$right--;
}
}
}
// UTILITY FUNCTIONS
function swap(&$a, &$b)
{
$temp = $a;
$a = $b;
$b = $temp;
}
// Driver Code
$arr = array(12, 34, 45, 9, 8, 90, 3);
$arr_size = count($arr);
segregateEvenOdd($arr, $arr_size);
echo "Array after segregation ";
for ($i = 0; $i < $arr_size; $i++)
echo $arr[$i]." ";
// This code is contributed
// by rathbhupendra
?>
Javascript
<script>
// javascript program to segregate even
// and odd elements of array
function segregateEvenOdd(arr)
{
/* Initialize left and right indexes */
var 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]*/
var temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
/* Driver program to test above functions */
var arr = [12, 34, 45, 9, 8, 90, 3];
segregateEvenOdd(arr);
document.write("Array after segregation ");
for (i = 0; i < arr.length; i++)
document.write(arr[i]+" ");
// This code is contributed by 29AjayKumar
</script>
Producción
Array after segregation 12 34 90 8 9 45 3
Complejidad de tiempo: O(n)
Implementación alternativa ( partición Lomuto ):
C++
// A Lomuto partition based scheme to segregate
// even and odd numbers.
#include <iostream>
using namespace std;
// Function to rearrange the array in given way.
void rearrangeEvenAndOdd(int arr[], int n)
{
// Variables
int j = -1;
// Quick sort method
for (int i = 0; i < n; i++) {
// If array of element
// is odd then swap
if (arr[i] % 2 == 0) {
// increment j by one
j++;
// swap the element
swap(arr[i], arr[j]);
}
}
}
int main()
{
int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };
int n = sizeof(arr) / sizeof(arr[0]);
rearrangeEvenAndOdd(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// This code is contributed by devagarwalmnnit
Java
// A Lomuto partition based scheme to segregate
// even and odd numbers.
import java.io.*;
class GFG
{
// function to rearrange the array in given way.
static void rearrangeEvenAndOdd(int arr[], int n)
{
// variables
int j = -1,temp;
// quick sort method
for (int i = 0; i < n; i++) {
// if array of element
// is odd then swap
if (arr[i] % 2 == 0) {
// increment j by one
j++;
// swap the element
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
// Driver code
public static void main(String args[])
{
int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };
int n = arr.length;
rearrangeEvenAndOdd(arr, n);
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// This code is contributed by Nikita Tiwari.
Python3
# A Lomuto partition based scheme to # segregate even and odd numbers. # function to rearrange the # array in given way. def rearrangeEvenAndOdd(arr, n) : # variables j = -1 # quick sort method for i in range(0, n) : # if array of element # is odd then swap if (arr[i] % 2 == 0) : # increment j by one j = j + 1 # swap the element temp = arr[i] arr[i] = arr[j] arr[j] = temp # Driver code arr = [ 12, 10, 9, 45, 2, 10, 10, 45 ] n = len(arr) rearrangeEvenAndOdd(arr, n) for i in range(0,n) : print( arr[i] ,end= " ") # This code is contributed by Nikita Tiwari.
C#
// A Lomuto partition based scheme
// to segregate even and odd numbers.
using System;
class GFG
{
// function to rearrange
// the array in given way.
static void rearrangeEvenAndOdd(int []arr,
int n)
{
// variables
int j = -1, temp;
// quick sort method
for (int i = 0; i < n; i++) {
// if array of element
// is odd then swap
if (arr[i] % 2 == 0) {
// increment j by one
j++;
// swap the element
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
// Driver code
public static void Main()
{
int []arr = { 12, 10, 9, 45, 2,
10, 10, 45 };
int n = arr.Length;
rearrangeEvenAndOdd(arr, n);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by Sam007
PHP
<?php
// A Lomuto partition based scheme to
// segregate even and odd numbers.
// function to rearrange the array
// in given way.
function rearrangeEvenAndOdd(&$arr, $n)
{
// variables
$j = -1; $temp;
// quick sort method
for ($i = 0; $i < $n; $i++)
{
// if array of element
// is odd then swap
if ($arr[$i] % 2 == 0)
{
// increment j by one
$j++;
// swap the element
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
}
}
// Driver code
$arr = array( 12, 10, 9, 45, 2, 10, 10, 45 );
$n = sizeof($arr);
rearrangeEvenAndOdd($arr, $n);
for ($i = 0; $i < $n; $i++)
echo($arr[$i] . " ");
// This code is contributed by Code_Mech.
Javascript
<script>
// A Lomuto partition based scheme to segregate
// even and odd numbers.
// Function to rearrange the array in given way.
function rearrangeEvenAndOdd(arr, n)
{
// Variables
var j = -1, temp;
// Quick sort method
for(i = 0; i < n; i++)
{
// If array of element
// is odd then swap
if (arr[i] % 2 == 0)
{
// Increment j by one
j++;
// Swap the element
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
// Driver code
var arr = [ 12, 10, 9, 45, 2, 10, 10, 45 ];
var n = arr.length;
rearrangeEvenAndOdd(arr, n);
for(i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by gauravrajput1
</script>
Producción
12 10 2 10 10 45 9 45
Complejidad de tiempo: O(n)
Implementación alternativa (usando partición estable ):
Para implementar el problema anterior, usaremos stable_partition en C++. El algoritmo stable_partition() organiza la secuencia definida por inicio y final de modo que todos los elementos para los que el predicado especificado por pfn devuelve verdadero vienen antes de aquellos para los que el predicado devuelve falso. La partición es estable. Esto significa que se conserva el orden relativo de la secuencia.
Sintaxis:
template BiIter stable_partition(BiIter start, BiIter end, UnPred pfn);
Parámetros:
start: the range of elements to reorder end: the range of elements to reorder pfn: User-defined predicate function object that defines the condition to be satisfied if an element is to be classified. A predicate takes single argument and returns true or false. Return Value: Returns an iterator to the beginning of the elements for which the predicate is false.
Esta función intenta asignar un búfer temporal. Si la asignación falla, se elige el algoritmo menos eficiente.
A continuación se muestra la implementación de la lógica anterior.
Código:
C++14
// CPP program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to rearrange the array in given way.
void rearrangeEvenAndOdd(vector<int>v)
{
// Using stable partition with lambda expression
stable_partition(v.begin(), v.end(),
[](auto a) { return a % 2 == 0; });
for (int num : v)
cout << num << " ";
}
// Driver Code
int main()
{
vector<int> v = { 12, 10, 9, 45, 2, 10, 10, 45 };
// Function Call
rearrangeEvenAndOdd(v);
return 0;
}
// This code is contributed by Chirag Shilwant
Producción
12 10 2 10 10 9 45 45
Complejidad del tiempo:
Si hay suficiente memoria extra disponible, lineal en la distancia entre el primero y el último, es decir ( O(N) , donde N es la distancia entre el primero y el último). Aplica el predicado (es decir, el tercer parámetro del código anterior) exactamente una vez a cada elemento y realiza hasta ese número de movimientos de elementos.
De lo contrario, realiza hasta N*log(N) intercambios de elementos (donde N es la distancia anterior). También aplica el predicado exactamente una vez a cada elemento.
Implementación alternativa:
- Usando dos punteros i y j , señalaré el índice 0 y j señalará el último índice.
- Ejecute un bucle while; si a[i] es impar y a[j] es par, entonces los intercambiaremos; de lo contrario, disminuiremos j.
Código:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to segregate
void segregate(int a[], int n)
{
int i = 0, j = (n - 1);
// Iterate while j >= i
while (j >= i) {
// Check is a[i] is even
// or odd
if (a[i] % 2 != 0)
{
if (a[j] % 2 == 0)
{
// Swap a[i] and a[j]
swap(a[i], a[j]);
i++;
j--;
}
else
j--;
}
else
i++;
}
for (int i = 0; i < n; i++)
cout << a[i] << " ";
}
// Driver Code
int main()
{
int a[] = { 1,2,3,4,5,6 };
int n = sizeof(a) / sizeof(a[0]);
// Function Call
segregate(a, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to segregate
static void segregate(int a[], int n)
{
int i = 0, j = (n - 1);
// Iterate while j >= i
while (j >= i)
{
// Check is a[i] is even
// or odd
if (a[i] % 2 != 0)
{
if (a[j] % 2 == 0)
{
// Swap a[i] and a[j]
a = swap(a, i, j);
i++;
j--;
}
else
j--;
}
else
i++;
}
for(i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
static int[] swap(int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 2, 3, 4, 5, 6 };
int n = a.length;
// Function Call
segregate(a, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to segregate def segregate(a, n): i = 0 j = (n - 1) # Iterate while j >= i while (j >= i): # Check is a[i] is even # or odd if (a[i] % 2 != 0): if (a[j] % 2 == 0): # Swap a[i] and a[j] a[i], a[j] = a[j], a[i] i += 1 j -= 1 else: j -= 1 else: i += 1; for i in range(n): print(a[i], end = " ") # Driver Code a = [ 1, 2, 3, 4, 5, 6 ] n = len(a) segregate(a, n) # This code is contributed by rag2127
C#
// C# program for the above approach
using System;
class GFG
{
// Function to segregate
static void segregate(int[] a, int n)
{
int i = 0, j = (n - 1);
// Iterate while j >= i
while (j >= i)
{
// Check is a[i] is even
// or odd
if (a[i] % 2 != 0) {
if (a[j] % 2 == 0) {
// Swap a[i] and a[j]
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
else
j--;
}
else
i++;
}
for (i = 0; i < n; i++)
Console.Write(a[i] + " ");
}
// Driver Code
public static void Main(string[] args)
{
int[] a = { 1, 2, 3, 4, 5, 6 };
int n = a.Length;
// Function Call
segregate(a, n);
}
}
// This code is contributed by ukasp.
Javascript
// JAVASCRIPT program for the above approach
import java.util.*;
class GFG{
// Function to segregate
static void segregate(int a[], int n)
{
int i = 0, j = (n - 1);
// Iterate while j >= i
while (j >= i) {
// Check is a[i] is even
// or odd
if (a[i] % 2 != 0)
{
if (a[j] % 2 == 0)
{
// Swap a[i] and a[j]
a = swap(a,i,j);
i++;
j--;
}
else
j--;
}
else
i++;
}
for (i = 0; i < n; i++)
System.out.print(a[i]+ " ");
}
static int[] swap(int []arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1,2,3,4,5,6 };
int n = a.length;
// Function Call
segregate(a, n);
}
}
// This code contributed by Princi Singh
Producción
6 2 4 3 5 1
Complejidad de tiempo: O(N)
Complejidad espacial: O(1)
Referencias:
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
Escriba comentarios si encuentra que el código/algoritmo anterior es incorrecto, o encuentre mejores formas de resolver el mismo problema.
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