In this article, we will discuss different ways to sort an array of std::pair in C++.

**Table Of Contents**

## Problem Statement

In this case, we are given an array of pairs, which needs to be sorted according to our requirements. Now, Lets consider an example, where you need to sort all pairs in increasing order of their first element. Pairs with same first value will be sorted based on the second values. For example,

Suppose we have an array of pairs like this,

// Initiating array of pairs with elements pair<int,int> arr[] = { make_pair(0, -7), make_pair(8, 6), make_pair(100, -1), make_pair(8, -4), make_pair(900, 10)};

We want to sort this array of pairs based on first value of pairs. Pairs with similar first values, should be sorted by the second value. Sorted output should be like this,

0 -7 8 -4 8 6 100 -1 900 10

There are various ways to to sort an array of pairs. Let’s discuss them one by one.

## Sort Array of Pairs using STL sort() function

The **sort()** in STL accepts 3 arguments. First two are the starting and ending address of the array, that need to be sorted. The last argument is the address of compare function which will be used for comparing pairs while sorting the array.

### Frequently Asked:

- Check if all elements of Array matches a Condition in C++
- Check if Any value in Array is greater than a Value in C++
- How to Check if element exist in array in C++?
- Check if Any element in Array matches a condition in C++

### Using Normal Function as argument in sort()

We will impliment sorting in main function. The **compare_pair()** function will return true if the second argument is greater than the first one. We can use this **compare_pair()** function as the comparator in sort() function, while sorting array of pairs.

`Note: We can get first element of pair with 'first' and second element with 'second'.`

`Time Complexity: O(nlog(n))`

`Space Complexity: O(1)`

**Example**

#include <iostream> #include <algorithm> using namespace std; // The function will return 1 if pair2 > pair1 else 0 bool compare_pair( const pair<int,int> &pair1, const pair<int,int> &pair2) { int result = 0; if( (pair2.first > pair1.first) || ((pair2.first == pair1.first) && (pair2.second > pair1.second)) ) { result = 1; } return result; } int main() { // Initiating array of pairs with elements pair<int,int> arr[] = { make_pair(0, -7), make_pair(8, 6), make_pair(100, -1), make_pair(8, -4), make_pair(900, 10)}; size_t len = sizeof(arr)/sizeof(arr[0]); // Calling sort() function with user defined // compare function 'compare_pair' sort(arr, arr+len, &compare_pair); // Printing Output for(int i=0;i<len;i++) { cout<<arr[i].first<<' '<<arr[i].second<<endl; } }

**Output**

0 -7 8 -4 8 6 100 -1 900 10

### Using Lambda Function as argument in sort()

In the above solution, we can also use the lambda function instead of normal function as the sort() function argument. For example,

#include <iostream> #include <algorithm> using namespace std; int main() { // Initiating array of pairs with elements pair<int,int> arr[] = { make_pair(0, -7), make_pair(8, 6), make_pair(100, -1), make_pair(8, -4), make_pair(900, 10)}; size_t len = sizeof(arr)/sizeof(arr[0]); // Calling sort() function with a lambda function // as the comparator sort(arr, arr+len, [](const pair<int,int> &pair1, const pair<int,int> &pair2){ int result = 0; if( (pair2.first > pair1.first) || ((pair2.first == pair1.first) && (pair2.second > pair1.second)) ) { result = 1; } return result; }); // Printing Output for(int i=0;i<len;i++) { cout<<arr[i].first<<' '<<arr[i].second<<endl; } }

**Output**

0 -7 8 -4 8 6 100 -1 900 10

## Sort Array of Pairs using Bubble sort

In this approach we will explicitly check each element in pair while determining which pair is greater. We will impliment bubble sort algorithm in **bubble_sort()** function.

`Time Complexity: O(n^2)`

`Space Complexity: O(n)`

**Example**

#include <iostream> using namespace std; void bubble_sort(pair<int,int>* arr, int len) { pair<int,int> temp; for (int i = 0; i < len; i++) { for (int j = 0; j + 1 < len - i; j++) { // Swaping if first pair is greater than second pair. if (arr[j].first > arr[j + 1].first) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } else if (arr[j].first == arr[j + 1].first && arr[j].second > arr[j + 1].second) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { // Initiating array of pairs with elements pair<int,int> arr[] = { make_pair(0, -7), make_pair(8, 6), make_pair(100, -1), make_pair(8, -4), make_pair(900, 10)}; size_t len = sizeof(arr)/sizeof(arr[0]); // Calling bubble_sort() function bubble_sort(arr, len); // Printing Output for(int i=0;i<len;i++) { cout<<arr[i].first<<' '<<arr[i].second<<endl; } }

**Output**

0 -7 8 -4 8 6 100 -1 900 10

## Summary

In this article, we have seen that how to compare pairs and sort the array of pairs using different techniques. We also learned that how we can access elements of pair and how we can create array of pairs.