Introduction
Problem statement
We are given an array. Our task is to sort all even numbers in the array without changing the position of odd elements
Sample examples
Input1: a[] = [ 6, 5, 4, 9, 7, 2, 5]
Output1: 2 5 4 9 7 6 5
Input2: a[] = [ 2, 3, 6, 4, 3, 8, 1]
Output2: 2 3 4 6 3 8 1
Also see, Rabin Karp Algorithm
Approach
We want to sort all even numbers in the array without changing the order of the odd elements. So the idea is simple, we store all the even numbers from the given array to another temporary container and then sort that temporary container.
The temporary container contains all even numbers from the given array in sorted form.
Finally, we replace the even numbers from the given array with the even numbers in the temporary container one by one.
Algorithm
- Create a temp vector.
- Traverse the given array. If the element is an even number, push the element into the temp vector else move to the next element.
- Sort the temp vector.
- Finally, replace all the elements from the temp vector with the even numbers in the given array one by one.
Let’s understand the above approach with an example:
Input: a[] = [ 6, 5, 4, 9, 7, 2, 5]
- Push all the even numbers in the temp vector.
temp = {6, 4, 2}
- Sort the temp vector.
temp ={2, 4, 6}
- Replace all the even numbers in the array with the numbers in the temp vector.
a[] = [ 2, 5, 4, 9, 7, 6, 5 ] // all even numbers sorted
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
void sort_even(int a[], int n)
{
vector<int> temp; // temporary container
for (int i = 0; i < n; i++)
{
if (a[i] % 2 == 0)
temp.push_back(a[i]);
}
sort(temp.begin(), temp.end()); //sorting the temporary container
int idx = 0;
for (int i = 0; i < n; i++) // replacing the numbers
{
if (a[i] % 2 == 0)
{
a[i] = temp[idx];
idx++;
}
}
}
int main()
{
int a[] = {6, 5, 4, 9, 7, 2, 5}; //given array
int n = sizeof(a) / sizeof(a[0]); // size of array
sort_even(a, n);
for (int i = 0; i < n; i++) // printing the modified array
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
Output:
2 5 4 9 7 6 5 Complexity Analysis
Time complexity: We are using the sort function, so the time complexity is O(n*logn), where n is the number of elements in the given array.
Space complexity: O(n), using a temp vector to store all the even elements.
Check out this array problem - Merge 2 Sorted Arrays
34+ registered 
