Sort all even numbers in ascending order and odd numbers in descending order

Problem: Given an array of integers (both odd and even), sort them in such a way that the first part of the array contains odd numbers sorted in descending order, rest portion contains even numbers sorted in ascending order.

Input: arr = {0, 4, 5, 3, 7, 2, 1}
Output: {7, 5, 3, 1, 0, 2, 4}

Input: arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Output: {9, 7, 6, 5, 3, 1, 2, 4, 8, 10}

Method 1:

• First we segregate all odd numbers to left side of array and even numbers on other side.
• Finally we sort the left part in descending order and second part in ascending order.

#include <bits/stdc++.h>
using namespace std;

/* driver function */
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(arr)/sizeof(arr[0]);

    int l = 0, h = n-1, o = 0;

    /* segregating all odd numbers to left and right 
       numbers to other side */
    while(l < h)
    {
        while(arr[l]%2!=0)
        {
            l++;
            o++;
        }

        while(arr[h]%2==0 && l < h)
        {
            h--;
            e++;
        }
    
        if(l < h)
            swap(arr[l], arr[h]);
    }

    /* sorting odd numbers in descending other */
    sort(arr, arr + o, greater<int>());
    sort(arr + o, arr + n);

    for (int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
    cout<<"\n";

    return 0;
}

Output:

9 7 5 3 1 2 4 6 8 10

Time Complexity: O(n)

Method 2: In this method

• We first make all odd numbers negative.
• Sort the array.
• Revert the changes (making odd number negative) to get required result.

#include <bits/stdc++.h>
using namespace std;

/* driver function */
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(arr)/sizeof(arr[0]);

    /* make all the odd numbers negative */
    for (int i = 0; i < n; i++)
    {
        if(arr[i]%2!=0)
        {
            arr[i] = -arr[i];
        }
    }

    /* sorting the array */
    sort(arr, arr + n);

    /* reverting back the changes made in above step */ 
    for (int i = 0; i < n; i++)
    {
        if(arr[i]%2!=0)
        {
            arr[i] = -arr[i];
        }
        else
       {
           break;
       }
    }

    for (int i = 0; i < n; i++)
        cout<<arr[i]<<" ";
    cout<<"\n";

    return 0;
}

Output:

9 7 5 3 1 2 4 6 8 10

Time Complexity: O(n)