Sorting and Comparing Elements

Sometimes, having all of the values arranged in the same order makes a collection of values quite useful. To that end, the standard library provides std::sort. Sort rearranges the elements of an iterator, so every one compares less than or equal to the one after it, according to the ordinary < operator unless you specify something else.

Imagine a std::vector containing five integer values in any random order.

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 40, 10, 50, 20, 30 };

    // Call this function with the provided arguments
    std::sort(v.begin(), v.end());

    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';

    return 0;
}

Before the call, the vector stores 40 10 50 20 30. std::sort is given the pair of iterators indicating the beginning and end of the entire container. It compares neighbors, swapping if necessary, repeatedly until the entire range is sorted in a non decreasing order.

After the call, the vector contains 10 20 30 40 50, which are printed by the loop.

Equal elements may not maintain their original relative order (this is called a stable sort): the implementation may rearrange equal values in any way.

The algorithm remains the same for any data that can be compared with <. If the default comparison operation isn't quite what you want, you can pass a function that takes two arguments and returns true if the first should come before the second. For example, to sort the same integers in reverse order, you could use a named comparison function like so:

#include <algorithm>
#include <iostream>
#include <vector>

bool isGreater(int a, int b)
{
    return a > b;
}

int main()
{
    std::vector v{ 40, 10, 50, 20, 30 };

    // Sort this range using the requested ordering
    std::sort(v.begin(), v.end(), isGreater);

    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';

    return 0;
}

The user defined predicate isGreater takes two integers, named a and b. It returns true exactly when a is greater than b, which means that larger values come before smaller ones. std::sort uses it to compare pairs of vector elements.

When the algorithm completes, we obtain the values 50 40 30 20 10 in the vector and that sequence is printed.

The sequence of comparisons and swaps is unchanged, only the interpretation of "comes before" is different.

The predicate you supply has to impose a strict weak ordering. If it doesn't, for example, if it returns true for both a < b and b < a, then std::sort's behavior is undefined. Here's an example of a faulty comparison:

#include <algorithm>
#include <iostream>
#include <vector>

bool isLessOrEqual(int a, int b)
{
    return a <= b;
}

int main()
{
    std::vector v{ 4, 2, 3, 1 };

    std::sort(v.begin(), v.end(), isLessOrEqual);   // not strict

    // Visit each element in the range directly
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';

    return 0;
}

Since isLessOrEqual will return true when both arguments are equal, the order is no longer strict. On many implementations, the program will seem to sort the values, although the C++ standard makes no guarantees on the result, the vector could end up in whatever state, and further use could crash or produce nonsensical results. The safe form is to use a strict relation such as < or >.

Sometimes after a sort, you want to verify that the sequence is really sorted. This is what the algorithm std::is_sorted does and returns a Boolean:

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 10, 20, 30, 40, 50 };

    // Query this type property at compile time
    if (std::is_sorted(v.begin(), v.end()))
        std::cout << "the sequence is sorted\n";
    else
        std::cout << "the sequence is not sorted\n";

    return 0;
}

The call compares consecutive pairs and yields true only if all values are less than or equal to the following one. Here, all pairs work out, and the program prints this good message. When sorting with a custom comparison, you have to give the same one to std::is_sorted; otherwise, the test will apply the wrong rule.

The algorithm std::sort requires random access iterators, hence it cannot operate over std::list. When you pass an iterator to the call that does not implement the required functionality, it will not compile. The algorithm may also reorder equal elements, and hence your code that depends on the relative order of equal elements should call std::stable_sort instead. Both algorithms move elements, and therefore any iterators to those elements that existed before the call become invalid.

The picture is therefore simple: use a pair of random access iterators, which delimit the sequence, and choose whether default comparison with < does the job or if a more specific strict comparison function is needed before calling std::sort. After the call completes, the sequence is ordered and consecutive elements respect the selected comparison operator, thus the next step can begin.

#include <algorithm>
#include <iostream>
#include <vector>

bool isGreater(int a, int b)
{
    return a > b;
}

int main()
{
    std::vector v{ 40, 10, 50, 20, 30 };

    // Sort this range using the requested ordering
    std::sort(v.begin(), v.end(), isGreater);

    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';

    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>

bool isGreater(int a, int b)
{
    return a > b;
}

int main()
{
    std::vector v{ 40, 10, 50, 20, 30 };

    // Sort this range using the requested ordering
    std::cout << "Before: ";
    for (int n : v) std::cout << n << ' ';
    std::cout << '\n';
    std::sort(v.begin(), v.end(), isGreater);

    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';

    return 0;
}

Before: 40 10 50 20 30 
50 40 30 20 10