Given an array arr[] of size N, the task is to segregate even and odd numbers. Print all even numbers first, and then odd numbers.
Examples:
Input: arr[] = {8, 22, 65, 70, 33, 60, 2, 34, 43, 21}
Output: {8, 22, 70, 60, 2, 34, 65, 33, 43, 21}Input: arr[] = {18, 52, 37, 70, 3, 63, 2, 34}
Output: {18, 52, 70, 2, 34, 37, 3, 63}
Linear Approach: This problem can be seen as a variation of the Dutch National Flag Problem. Refer to the previous post for all the linear approaches to solve the problem.
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach using stable_partition() Function: The stable_partition() algorithm arranges the sequence defined by start and end such that all elements for which the predicate, specified by user-defined predicate function, returns True, precedes the ones for which the function returns False. The partitioning is stable. Therefore, the relative ordering of the sequence is preserved.
Syntax:
template
BiIter stable_partition(BiIter start, BiIter end, UnPred pfn)
Parameters:
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 a single argument and returns True or False.
Return Value: Returns an iterator to the beginning of the elements for which the predicate is false.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to segregate// odd and even numbersvoid 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 Codeint main(){ // Given array arr[] vector<int> arr = { 18, 52, 37, 70, 3, 63, 2, 34 }; // Function Call segregate(arr); return 0;} |
Java
// Java program to implement// the above approachimport 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 numbersstatic 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 Codepublic 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
# Python3 program to implement# the above approach# Function to segregate# odd and even numbersdef 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 Codeif __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#
// C# program to implement// the above approachusing 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 numbersstatic void segregate(int[] arr){ // Using stable partition // with lambda expression stable_partition(arr);}// Driver Codepublic 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 |
Javascript
<script>function stable_partition( 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] int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } return arr;}var arr = [ 18, 52, 37, 70,3, 63, 2, 34 ]; segregateEvenOdd(arr); for (i = 0; i < arr.length; i++) document.write(arr[i]+" ")// This code is contributed by laxmigangarajula03</script> |
18 52 70 2 34 37 3 63
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
