Sort all even numbers in the Array without changing the order of odd elements

Sandeep kamila
Last Updated: May 13, 2022

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

 

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.

Frequently asked questions

Q1. How to sort an array of odd and even numbers?

Ans: Algorithm:

  • Create two index variables with the values left=0 and right=arr.length-1.
  • Increase the value of the left variable until it reaches an odd number.
  • Adjust the right variable until the result is an even number.
  • Swap arr[left] and arr[right] if left and right are the same.
  • In the end, you'll notice that the left side has even numbers, and the right side has odd numbers.

 

Q2. In an array, how do you find an even number?

Ans: By getting the remainder of each element and checking if it is divided by two or not, we can print odd and even numbers from a given array. It is an even number if it is completely divided by two. Otherwise, it is an odd number.

 

Q3. Which sorting algorithm is best for large data?

Ans: Insertion sort is the fastest for large numbers of data sets. It is a rare occurrence in practical sorting. It's worth noting that randomised Quicksort reduces the likelihood of worst-case scenarios, which is the case for in-order data if the pivot point in Quicksort is set to the first element.

Key Takeaways

This article discussed how to sort all even numbers in the array without changing the positions of odd elements with the help of a temporary container with examples for a better understanding and its code in C++.

If you are a beginner, interested in coding and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think