How to Sort an Array of pairs in C++?

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.

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.