1.
Introduction
1.1.
sort() in C++ STL
1.2.
Code in C++ using sort() function without third parameter
1.3.
Code in C++ using sort function with third parameter ( greater<int>() )
2.
Problem statement
2.1.
Sample Examples
2.2.
Approach
2.3.
Code in C++
2.3.1.
Complexity Analysis
3.
4.
Key Takeaways
Last Updated: Mar 27, 2024

# How to sort and separate even and odd numbers in an array using a custom comparator?

## 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``

## 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.

Q1. Is STL's sort stable?

Ans: Introsort is typically used by the sort() function. As a result, sort() may or may not preserve the physical order of semantically equivalent values. Mergesort is usually used by the stable sort() function. As a result, stable sort() guarantees that the physical order of semantically equivalent values is preserved.

Q2. In STL, how do I sort a queue?

Ans: Sorting a Queue without Taking Up Additional Space

• Enqueue(): Pushes an item to the front of the queue. This function is known as push in the C++ STL queue ().
• Dequeue (): Removes an item from the front of the queue. This function is known as pop in the C++ STL queue ().
• isEmpty(): Determines whether or not a queue is empty. This function is known as empty in the C++ STL queue ().

Q3. What is insertion sort, and how does it work?

Ans: Insertion sort is a straightforward sorting algorithm that works similarly to how you sort cards in your hands. The array is divided into two parts, one sorted and the other unsorted. The values from the unsorted part are selected and placed in the sorted part in the proper order.

Also Read - Strong number in c

## Key Takeaways

This article discussed the sort() function, how to sort and separate even and odd numbers using a comparator function with complete explanations, examples and code in C++.

Check out the following problems -

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!