Introduction
This blog will discuss the approach to sorting and separating even and odd numbers using a custom comparator. Before jumping into the problem, let’s first learn the sort() function in C++ STL.
sort() in C++ STL
C++ STL provides a sort function that sorts an array/vector or string (items with random access).
It takes three parameters:
- The first parameter points to the beginning element from where it needs to be sorted.
- The second parameter points to the element beyond the last element up to which it needs to be sorted.
-
The third parameter in the sort function is optional and can sort an array/vector or string in a particular order.
If we don’t use the third parameter, the array/vector will get sorted in ascending order.
Code in C++ using sort() function without third parameter
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[] = { 6, 5, 4, 9, 7, 2, 5}; //given array
int n = sizeof(a) / sizeof(a[0]); // size of array
sort(a, a + n);
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
Output:
2 4 5 5 6 7 9 // ascending order
Code in C++ using sort function with third parameter ( greater<int>() )
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[] = { 6, 5, 4, 9, 7, 2, 5}; //given array
int n = sizeof(a) / sizeof(a[0]); // size of array
sort(a, a + n, greater<int>());
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
Output:
9 7 6 5 5 4 2 // descending order
Also read, Euclid GCD Algorithm
Problem statement
We are given an array. Our task is to sort and separate even and odd numbers in an array using a custom comparator.
Sample Examples
Example 1:
Input: a[] = [ 6, 5, 4, 9, 7, 2, 5]
Output: 5 5 7 9 2 4 6
Explanation:
Sorted odd numbers Sorted even numbers.
Example 2:
Input: a[] = [ 2, 3, 6, 4, 3, 8, 1]
Output: 1 3 3 2 4 6 8
Explanation:
Sorted odd numbers Sorted even numbers.
Approach
We want to sort and separate all the even and odd numbers in the given array, so we use the third parameter (comparator) in the sort function.
We can write our comparator and pass it in as a third parameter. This "comparator" function returns a boolean value that tells us whether the passed "first" argument should be placed before the passed "second" argument or not.
If the compare function returns true, the first argument is placed before the second argument and vice versa.
Let’s suppose we place all the odd numbers first then all the even numbers in sorted form.
Compare() function:
- If both the parameters are odd or even, place the smaller number before the larger number.
- If the first number is even and the other is odd, place the even number after the odd number.
-
If the first number is odd and the other is even, place the odd number before the even number.
Let’s understand this with an example:
Suppose 6 and 7 are passed as an argument in the compare function (comparator). As 6 is even and 7 is odd, 6 is placed after 7.
Code in C++
#include<bits/stdc++.h>
using namespace std;
bool compare(int a, int b)
{
if ((a % 2 == 0 && b % 2 == 0) || (a % 2 != 0 && b % 2 != 0 ))
{
if (a < b)
return true;
else
return false;
}
if (a % 2 == 0)
return false;
else
return true;
}
int main()
{
int a[] = { 6, 5, 4, 9, 7, 2, 5}; //given array
int n = sizeof(a) / sizeof(a[0]); // size of array
sort(a, a + n, compare);
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
Output:
5 5 7 9 2 4 6
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(1), as we are using constant extra space.
39+ registered 