Last Updated: 8 Jul, 2022
Sort Odd Even
Easy
Asked in company
You are given a 0-indexed array ‘NUMS’ consisting of ‘N’ integers. Sort the array ‘NUMS’ in such a way that the first half of the array contains only odd numbers sorted in non-increasing order and the second half contains only even numbers sorted in non-decreasing order.
Example:
Input: ‘N’ = 4, ‘NUMS’ = [2, 5, 3, 6]
Output: [5, 3, 2, 6]
Sorting the odd numbers of the array ‘NUMS’ in non-increasing order, the result is 5, 3
Then, Sorting the even numbers in non-decreasing order, the result is 2, 6.
Since the final array should contain the odd numbers in non-increasing order in the first half and even numbers in non-decreasing order in the other half.
So, the final array is [5, 3, 2, 6].
Input Format :
The first line will contain the integer 'T', denoting the number of test cases.
The first line of each test case contains an integer ‘N’ where ‘N’ denotes the length of the array ‘NUMS’.
The second line of each test case contains ‘N’ integers.
Output format :
For each test case, you don’t need to return anything just rearrange the given array.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
Sum of ‘N’ <= 10^5
1 <= NUMS[i] <= 10^9
Time Limit: 1 sec
Approaches
In the naive approach, We store the odd numbers in an extra array and the even numbers in another array. Sort them separately and then replace the first half of ‘NUMS’ with the odd numbers array and the other half with the even numbers array.
The steps are as follows:-
Function sortOddEven(vector<int>& nums):
- Declare two arrays 'ODD', 'EVEN' to store odd and even values of 'NUMS'.
- Iterate from i = 0...'N'-1:
- If the value of 'NUMS' at ‘i’th index is odd push that value into the 'ODD' array.
- Else if it is even push it into the 'EVEN' array.
- Sort the 'ODD array in non-increasing order.
- Sort the 'EVEN' array in non-decreasing order.
- Initialize three variable 'oddIdx', 'evenIdx', 'i' to 0.
- Iterate over the 'ODD' array and assign its value to 'NUMS' at 'i' then increment 'i' by 1.
- Iterate over the 'Even' array and assign its value to 'NUMS' at 'i' then increment 'i' by 1.
We can partition the array ‘NUMS’ in place in such a way that the first half contains only odd numbers and the second half contains only even numbers. The idea is to use a partitioned index that initially points to the starting of the array. Iterate over the array if any odd number is encountered swap it with the partitioned Index and then increment the partitioned index by 1. After partitioning sort the array from start to partitioned index in non-increasing order and the rest in non-decreasing order.
The steps are as follows:-
Function sortOddEvenvector<int>& nums):
- Initialize a variable 'PIDX' with 0 to store the partition index.
- Run a loop from i=0...'N'-1:
- If the value of 'NUMS' at 'i' is odd then swap it with of value of 'NUMS' at 'PIDX' and the increment 'PIDX' by 1.
- Sort the arrays 'NUMS' from 0 to 'PIDX-1' in non-increasing order.
- Sort the arrays 'NUMS' from 'PIDX' to 'N-1' in non-decreasing order.