Beginners guide to the std::sort() function

Score: 4.3/5 (1226 votes)

Important Information

Now before we start I would like to state that I will be using features that are only available on C++11 compilers. If you don't have a C++11 or don't know if your compiler supports it, I would recommend doing this. Head on over to CodeBlocks and download their IDE. It comes with a C++11 compiler and you can enable it by going to settings->compiler->compiler settings->compiler flags-> and then you should see a checkbox that says something like Have g++ follow the C++11 ISO C++ language standard. Enable that and click ok and you should be good to go.

What It Looks Like

The sort() function in the algorithm header can be a very useful tool to both new and experienced programmers. It's use is to sort containers like arrays and vectors.

The first example is what the function looks like. The second example is an optional overloaded function that includes a third parameter. First take a look at each of these functions and see if we can figure out what each parameter does.

Example 1 ~ std::sort(myvector.begin(), myvector.end())

Example 2 ~ std::sort(myvector.begin(), myvector.end(), myCompFunction)

About The Function

So let’s go dig into these and figure out what each does and why it does it.

Found in ~ #include <algorithm>

Parameter 1 myvector.begin() ~ The first parameter is where you will be putting a iterator(Pointer) to the first element in the range that you want to sort. The sort will include the element that the iterator points to.

Parameter 2 myvector.end() ~ The second parameter is almost like the first but instead of putting a iterator to the first element to sort you will be putting a iterator to the last element. One very important difference is that the search won’t include the element that this iterator points to. It is [First,Last) meaning it includes the first parameter in the sort but it doesn’t include the second parameter in the sort.

Parameter 3 myCompFunction() Optional ~ I will only give a brief description here, because I will be explaining this parameter in more detail later. The third parameter is used to define how you do the search. For example if you have a struct that has 3 different variables in it, how does the function know which one to sort? Or how does it know how it should sort it? This is what this parameter is for. I will explain this more in a bit.

Function Return ~ This function doesn’t return anything because it alters the container directly through iterators(Pointers).

Array Example

// sort() Example using arrays.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>

using namespace std;

const int SIZE = 7;

int main()
{
    int intArray[SIZE] = {5, 3, 32, -1, 1, 104, 53};

    //Now we call the sort function
    sort(intArray, intArray + SIZE);

    cout << "Sorted Array looks like this." << endl;
    for (size_t i = 0; i != SIZE; ++i)
        cout << intArray[i] << " ";

    return 0;
}

Things to know

When we use the sort function to sort an array our arguments will look a bit different then when we use it on a vector for example. In the example above when we pass in intArray as an argument we are telling the function to start the sort at the beginning of the array. If we wanted it to start the sort at the second element of the array we would do sort(intArray + 1, intArray + SIZE);. So when we do intArray + SIZE for the second argument we are telling the array to sort up to the last element in the array.

Using C++11 to simplify things

We can make sorting whole arrays even easier by using std::begin() and std::end(). std::begin() will return a iterator(pointer) to the first element in the array we pass it. Whereas std::end() will return a iterator(pointer) to one past the last element in the array we pass it. So we could call the sort function by passing it begin() and end() like so.

sort(begin(intArray), end(intArray));

Sorting Vectors and other STL Containers Example

Warning: Uses C++11 features.

// Vector Sorting Example.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main()
{
    // Warning this type of initialization requires a C++11 Compiler
    vector<int> intVec = {56, 32, -43, 23, 12, 93, 132, -154};
    vector<string> stringVec = {"John", "Bob", "Joe", "Zack", "Randy"};

    // Sorting the int vector
    sort(intVec.begin(), intVec.end());

    for (vector<int>::size_type i = 0; i != intVec.size(); ++i)
        cout << intVec[i] << " ";

    cout << endl;

    // Sorting the string vector
    sort(stringVec.begin(), stringVec.end());

    // Ranged Based loops. This requires a C++11 Compiler also
    // If you don't have a C++11 Compiler you can use a standard
    // for loop to print your vector.
    for (string &s : stringVec)
        cout << s << " ";

    return 0;
}

Things to know

First as you can see the sorting function works almost the same as on an array but we just have to pass our arguments a little differently. Since the first parameter in sort() accepts a iterator(pointer) to the first element we want to sort we can pass stringVec.begin() to it because .begin()returns a iterator to the first element. So it will start the sorting at the first element in the vector. The same goes for stringVec.end() for the second parameter because remember .end() is a iterator that points to one past the last element in the container. Remember the sort function sorts up to but not including what we pass in as the second parameter.

You also probably noticed that the sort works on things other then numbers. When we printed out the vector of strings it gave us a nice and neat vector that holds the names in their alphabetical order.

The Overloaded sort() With A Third Parameter.

The third parameter in the sort() function is actually a very useful feature. It allows us to define how the sort() function will actually perform the search. Sometimes you can get by with the normal version of sort(), but what if we wanted to change how the container was sorted by having it sort by descending order instead of ascending? Or what if we had a container full of a special type of class objects we created and need to sort that container a special way? Well this is where the third parameter comes in.

Making it sort by descending order example.

Warning: Uses C++11 Features

// Vector Sorting Descending Example.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// We need this function to define how to sort
// the vector. We will pass this function into the
// third parameter and it will tell it to sort descendingly.
bool wayToSort(int i, int j) { return i > j; }

int main()
{
    vector<int> intVec = {56, 32, -43, 23, 12, 93, 132, -154};
    
    // Do not include the () when you call wayToSort
    // It must be passed as a function pointer or function object
    sort(intVec.begin(), intVec.end(), wayToSort);

    for (int i : intVec)
        cout << i << " ";
    
    return 0;
}

The Function

First let’s look at the function. What we did is we created a function that will determine whether i > j every time it is called. The sort function will automatically assign an element to both i and j.

The function you make needs to have a return type of Boolean.

So when we define bool wayToSort(int i, int j) { return i > j; }, we are saying we wanted it to sort descending because i>j. Whereas ascending would be i<j.

Using the STL to simplify sorting in ascending or descending.

Another solution to the problem of getting it to sort descending is to use std::greater(), which would look like this.

sort(intVec.begin(), intVec.end(), greater<int>());

Sorting User Made Types.

For a lot of programs we aren’t storing just ints, strings, or doubles. Instead we are making complicated classes that have multiple number and string members and storing them in a container. So when we want to sort that container of our class objects we need to define a special function that will tell the sort() function how it should sort those objects.

So for my last example lets say we have a struct that represents a person and it looks like this.

struct Person
{
    string name;
    int age;
    string favoriteColor;
};

As you can see it has three members: name, age and color. Now let’s say we have a program that has a vector full of Person objects, and we need a way to be able to sort them by their name, age or favorite color at certain points in the program.

One way would be to make a function for each different way of sorting like in the example below. Those this is not the only way.

Warning: Uses C++11 Features

// Complicated Types Sorting Example.
// By Zereo 04/22/13
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct Person
{
    // Left out making a constructor for simplicity's sake.
    string name;
    int age;
    string favoriteColor;
};

// Sort Container by name function
bool sortByName(const Person &lhs, const Person &rhs) { return lhs.name < rhs.name; }

// Sort Container by age function
bool sortByAge(const Person &lhs, const Person &rhs) { return lhs.age < rhs.age; }

// Sort Container by favorite color
// We can just sort alphabetically and then it will group the
// color together.
bool sortByColor(const Person &lhs, const Person &rhs) { return lhs.favoriteColor < rhs.favoriteColor; }

// A global const variable to hold how many people to ask for input for.
const unsigned numberOfPeople = 2;

int main()
{
    // Make a vector that holds 5 blank Person Objects
    vector<Person> people(numberOfPeople);

    // This will ask for user input to populate the container
    // with 5 different indivuals.
    for (vector<Person>::size_type i = 0; i != numberOfPeople; ++i)
    {
        cout << "Person #" << i + 1 << " name: ";
        cin >> people[i].name;

        cout << "Person #" << i + 1 << " age: ";
        cin >> people[i].age;

        cout << "Person #" << i + 1 << " favorite color: ";
        cin >> people[i].favoriteColor;
    }

    cout << "\n\n";

    // Sort by name
    sort(people.begin(), people.end(), sortByName);
    for (Person &n : people)
        cout << n.name << " ";

    cout << endl;

    // Sory by age
    sort(people.begin(), people.end(), sortByAge);
    for (Person &n : people)
        cout << n.age << " ";

    cout << endl;

    // Sort by color
    sort(people.begin(), people.end(), sortByColor);
    for (Person &n : people)
        cout << n.favoriteColor << " ";

    return 0;
}

Things to know

Now I won’t be able to go into everything that was going on in that last example, but I will go through one of the functions and explain how it works.

Sort By Name Function

bool sortByName(const Person &lhs, const Person &rhs) 
{ 
    return lhs.name < rhs.name;
}

This function is actually very similar to the one we just made before except we changed two things. We changed the parameter types from int to type Person, and we also changed the return expression a bit.

First let’s go over the change to the parameters.

The reason why we had to change the parameters from int to Person, is because the container we are sorting is of type vector<Person>. And in order to be able to call the equation lhs.name < rhs.name the parameters would have to be of type Person so we can access the name members.

Secondly we changed the return equation to lhs.name < rhs.name. Can you guess what this equation is asking? Well what this is saying is basically this. Remember that both lhs and rhs are pointing to a separate element in the container (Like lhs is element 1 and rhs is element 2). So when we say lhs.name we are telling it to access element 1’s object and then access that objects name member. The same goes for rhs.name but is it accessing element 2’s object instead. So when we say to return lhs.name < rhs.name we are asking it if lhs’s object’s name less then rhs’s objects name.

The other functions are actually just the same but use the different members of the struct.

THE END ;p

Well that is all for this tutorial, though there is a lot more to learn about sorting with the STL. So if you are interested you can look below for some links to other things that relate to sort(). If you have any comments (Especially on any mistakes) on the article/tutorial please let me know I enjoy any type of feedback good or bad.

The same goes for any questions, if you don’t understand anything or the way I explained something didn’t make sense (More then likely ;p) please let me know through a reply here or through a PM. I would be glad to help answer any questions you have.

I am hoping to create some more tutorials shortly about how to use algorithms from the STL. Once I get them written up I will either add them to this Article or create a new one. Hope everyone liked it and thanks for reading,

Resources

Documentations

std::end()
std::begin()
std::sort()
std::stable_sort()
std::greater()
std::less()

Information

Ranged Based For Loops
Info on initialization in C++11

~ Zereo