Rearrange Array’s Even and Odd values in Ascending order C++

In this post we will understand the problem of rearranging the array’s even and odd values in Ascending order, then we will discuss the best possible approach and then write a C++ code to implement the solution. Let’s discuss the problem:

Given: An array of integers with equal number of even and odd values.

Problem: Arrange the given array in such a way that odd and even values come in alternate fashion in ascending order respectively.

• If the smallest value is Even then we have to print Even-Odd pattern.
• If the smallest value is Odd then we have to print Odd-Even pattern.

Let’s say an example for the same.

Examples:

Input: arr[] = {1, 3, 2, 5, 4, 7, 10}
Output: 1, 2, 3, 4, 5, 10, 7
Smallest value is 1(Odd) so output will be Odd-Even pattern.

Input: arr[] = {9, 8, 13, 2, 19, 14}
Output: 2, 9, 8, 13, 14, 19
Smallest value is 2(Even) so output will be Even-Odd pattern.

Solution:

• Sort the given array.
• Insert Even values in List-1 and Odd values in List-2.
• Now if the smallest value is even, then insert an even value from list 1 and odd value from list 2 to original array and so on.
• But if the smallest value is odd, then insert an odd value from list 2 and even value from list 1 to original array and so on.

Now let’s write a program to implement the above solution in C++ programming language.

C++ Program to rearrange Array’s Even and Odd values in Ascending order:

// C++ implementation of the above approach 
#include <bits/stdc++.h> 
using namespace std; 

void AlternateRearrange(int arr[], int n) 
{ 
    // Sort the array 
    sort(arr, arr + n); 

    vector<int> v1; // to insert even values 
    vector<int> v2; // to insert odd values 

    for (int i = 0; i < n; i++) 
        if (arr[i] % 2 == 0) 
            v1.push_back(arr[i]); 
        else
            v2.push_back(arr[i]); 

    int index = 0, i = 0, j = 0; 

    bool flag = false; 

    // Set flag to true if first element is even 
    if (arr[0] % 2 == 0) 
        flag = true; 

    // Start rearranging array 
    while (index < n) { 

        // If first element is even 
        if (flag == true) { 
            arr[index++] = v1[i++]; 
            flag = !flag; 
        } 

        // Else, first element is Odd 
        else { 
            arr[index++] = v2[j++]; 
            flag = !flag; 
        } 
    } 

    // Print the rearranged array 
    for (i = 0; i < n; i++) 
        cout << arr[i] << " "; 
} 

// Driver code 
int main() 
{ 
    int arr[] = { 9, 8, 13, 2, 19, 14 }; 
    int n = sizeof(arr) / sizeof(int); 
    AlternateRearrange(arr, n); 
    return 0; 
} 

OUTPUT:

2 9 8 13 14 19

Comment below in case  of any query, issues or suggestions regarding the problem discussed above.