Sort all even numbers in the Array without changing order of odd elements
Given an array arr[] of size N, the task is to sort all the even numbers in the array, without changing the order of odd elements
Examples:
Input: arr[] = {4, 7, 2, 11, 15}
Output: {2, 7, 4, 11, 15}
Explanation: Even numbers are sorted at their corresponding places, without changing the order of odd elements
Input: arr[] = {12, 6}
Output: {6, 12}
Approach: The task can be solved by segregating the even elements into another container say ‘evens‘, sort this container, and while iterating the array, replace the even elements with the sorted even elements stored in evens
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to get the required array void solve( int arr[], int n) { // Store even elements vector< int > evens; for ( int i = 0; i < n; i++) { if (arr[i] % 2 == 0) evens.push_back(arr[i]); } // Sort all even elements sort(evens.begin(), evens.end()); int l = 0; // Placing even elements in sorted order for ( int i = 0; i < n; i++) { if (arr[i] % 2 == 0) arr[i] = evens[l++]; } // Updated array for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // Driver Code int main() { int N = 5; int arr[N] = { 4, 7, 2, 11, 15 }; solve(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to get the required array static void solve( int []arr, int n) { // Store even elements ArrayList<Integer> evens = new ArrayList<Integer>(); for ( int i = 0 ; i < n; i++) { if (arr[i] % 2 == 0 ) evens.add(arr[i]); } // Sort all even elements Collections.sort(evens); int l = 0 ; // Placing even elements in sorted order for ( int i = 0 ; i < n; i++) { if (arr[i] % 2 == 0 ) arr[i] = evens.get(l++); } // Updated array for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } // Driver function public static void main(String []args) { int N = 5 ; int []arr = { 4 , 7 , 2 , 11 , 15 }; solve(arr, N); } } // This code is contributed by AnkThon |
Python3
# python program of the above approach # Function to get the required array def solve(arr, n): # Store even elements evens = [] for i in range ( 0 , n): if (arr[i] % 2 = = 0 ): evens.append(arr[i]) # Sort all even elements evens.sort() l = 0 # Placing even elements in sorted order for i in range ( 0 , n): if (arr[i] % 2 = = 0 ): arr[i] = evens[l] l + = 1 # Updated array for i in range ( 0 , n): print (arr[i], end = " " ) # Driver Code if __name__ = = "__main__" : N = 5 arr = [ 4 , 7 , 2 , 11 , 15 ] solve(arr, N) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to get the required array static void solve( int []arr, int n) { // Store even elements List< int > evens = new List< int >(); for ( int i = 0; i < n; i++) { if (arr[i] % 2 == 0) evens.Add(arr[i]); } // Sort all even elements evens.Sort(); int l = 0; // Placing even elements in sorted order for ( int i = 0; i < n; i++) { if (arr[i] % 2 == 0) arr[i] = evens[l++]; } // Updated array for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Driver function public static void Main() { int N = 5; int []arr = new int [] { 4, 7, 2, 11, 15 }; solve(arr, N); } } // This code is contributed by Samim Hossain Mondal |
Javascript
<script> // Javascript program for the above approach // Function to get the required array function solve(arr, n) { // Store even elements let evens = []; for (let i = 0; i < n; i++) { if (arr[i] % 2 == 0) evens.push(arr[i]); } // Sort all even elements evens.sort(); let l = 0; // Placing even elements in sorted order for (let i = 0; i < n; i++) { if (arr[i] % 2 == 0) arr[i] = evens[l++]; } // Updated array for (let i = 0; i < n; i++) document.write(arr[i] + " " ); } // Driver Code let N = 5; let arr = [ 4, 7, 2, 11, 15 ]; solve(arr, N); // This code is contributed by Samim Hossain Mondal. </script> |
Output
2 7 4 11 15
Time Complexity: O(NlogN)
Auxiliary Space: O(N)