Using sort() in C++ std Library

Introduction

Hey there! Today we are going to discuss the sort() function in the std library in C++.

For basics, Sorting is any process of ordering items systematically. These items could be elements of a sequence or any data structure.

In C++, the standard library provides a pre-defined and ready to use function sort() to carry out this sorting operation. So let’s get right into it.

The std::sort() Function in C++

The std::sort() function in C++ is a built-in function that is used to sort any form of data structure in a particular order. It is defined in the algorithm header file. The sort() function prototype is given below.

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Here, the function does not return anything. It just updates the elements/items from the first up to the last iterables or positions. The third parameter(optional) comp has to be a function that determines the order in which the elements are going to be sorted. When not specified, the sorting takes place in ascending order considering it to be the std::less<int>() function by default.

The sort() function uses a 3 fold hybrid sorting technique named Introsort. It is a combination of Quick Sort, Heap Sort, and Insertion Sort.

Sorting data using the sort() Function in C++

Now that we have gone through the basics of the sort() function, let us use it in our C++ program to sort some data structures(for example arrays).

1. Sorting in Ascending Order

As mentioned earlier, by default the sort() function sorts a set of items in ascending order when comp parameter is not mentioned.

So for the example below, we have passed just the first(starting) and last(ending) iterables to sort an array in ascending order.

#include<iostream>    
#include<algorithm>
using namespace std;
int main()
{  
    //array initialisation
    int demo[5] = {5, 4, 3, 2, 1};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"Before sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len);//Sorting demo array
     
    cout<<"\n\nAfter sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

Output:

Here, demo is the address of the first element and (demo + len) is the address of the last element of the given array. Hence considering comp as std::less<int>() function by default, the sort() function sorts the array in ascending order.

Note: the std::less<int>() function compares two arguments and returns True or False on the basis of whether the first one is less than the other.

2. Sorting in Descending Order

We can also sort a data structure using the sort() function in descending order by manipulating its third parameter. Let us see how.

In the code below we have used the std::greater<int>() function which acts exactly the opposite way the std::less<int>() function does. It compares its two arguments and returns True when the first one is greater than the other. Or else returns False.

#include<iostream>    
#include<algorithm>
using namespace std;
int main()
{  
    //array initialisation
    int demo[5] = {44, 22, 55, 33, 66};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"Before sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len, greater<int>());//Sorting demo array
     
    cout<<"\n\nAfter sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

We can also use a lambda function as the third parameter for the sort() function as shown below.

#include<iostream>    
#include<algorithm>
using namespace std;
int main()
{  
    //array initialisation
    int demo[5] = {44, 22, 55, 33, 66};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"Before sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len, [](int &e1, int &e2){ return e1>e2; });//Sorting demo array
     
    cout<<"\n\nAfter sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

Both the above examples generate the same output as given below. And sort the demo array in descending order successfully.

Output:

3. Sorting with User-Defined Order

The third parameter(comp) for the std::sort() function can also be a user-defined function that defines the order or sorting.

One should note that this function must return a boolean value(True/False).

For example in the code snippet below, we have tried to sort the elements of an array on the basis of the remainders they produce when divided by 10(using ‘%’ operator).

#include<iostream>    
#include<algorithm>
using namespace std;

//our function
bool My_func( int a, int b)
{	
	return (a%10)<(b%10);
}

int main()
{  
    //array initialisation
    int demo[5] = {18, 45, 34, 92, 21};
    
    int len = sizeof(demo)/sizeof(demo[0]);
     
    cout<<"Before sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
     
    std::sort(demo, demo + len, My_func);//Sorting demo array
     
    cout<<"\n\nAfter sorting array : ";
    for(int i=0; i<len; i++)
    {
        cout<<" "<<demo[i];
    }
    return 0;
}

Output:

As we can see from the above output, the demo array has been sorted successfully on the basis of (element%10) factor. With the help of our My_func() function.

Complexity of std::sort() in C++

The sort() function performs Nlog(N) comparisons for sorting N items. And hence for the worst-case scenario, it has an O(Nlog(N)) complexity.

Summing Up

So that’s it for this one. Today we understood the use and working of the sort() function in C++ standard library. Hope you had a clear understanding.

Please note that the sort() function can be used for data structures other than arrays too, like vectors, etc… For this tutorial, we have considered arrays for better understanding.

We recommend going through our C++ Tutorial.

For any further questions, feel free to use the comment below.

References

• std::sort() - C++ Documentation,
• Standard Template Library (STL) in C++,
• <algorithm> – C++ algorithm Library.