Sorting A Vector In C++

Here we’ll look at one of the most common data manipulation tasks - sorting. Specifically, we’ll be using the STL’s sort method.

Basics

To get the ball rolling, let’s see how to sort a vector of integers.

#include <iostream>   // std::cout
#include <algorithm>  // std::sort
#include <vector>     // std::vector

int main() {
    std::vector<int> foo = {5, 3, 10, 1, 7};  // Make values
    std::sort(foo.begin(), foo.end());        // Sort
    for(int &x : foo) std::cout << x << " ";  // Print
}

1 3 5 7 10

The sort() method signature requires three parameters

1. first - a random access iterator to the first position in the range to be sorted
2. last - a random access iterator to the last position in the range to be sorted
3. comp - a comparison function like func(A, B) that returns TRUE if A should come before B

In our simple example above, we left out the third parameter, comp, so the default comparison function (operator <) was used. And since we used foo.begin() and foo.end() for the first and last parameters, the entire vector was sorted. If we only wanted to sort the first three values, we could have done something like std::sort(foo.begin(), foo.begin() + 3);

Reverse Sort

How might we sort foo in reverse order? Insted of using forward iterators, foo.begin() and foo.end(), we can use backward iterators foo.rbegin() and foo.rend().

#include <iostream>   // std::cout
#include <algorithm>  // std::sort
#include <vector>     // std::vector

int main() {
    std::vector<int> foo = {5, 3, 10, 1, 7};  // Make values
    std::sort(foo.rbegin(), foo.rend());      // Reverse sort
    for(int &x : foo) std::cout << x << " ";  // Print
}

10 7 5 3 1

Custom Sort

Now suppose we wanted to sort the values using a custom criteria like the distance each number is to the number 5. In other words, the result should have numbers close to 5 in the front and numbers far from 5 in the back. In this case, we’ll need to define an “A vs B” binary comparison function to pass into the comp parameter of sort().

#include <iostream>   // std::cout
#include <algorithm>  // std::sort
#include <vector>     // std::vector
#include <cmath>      // std::abs

// Returns true if 'a' is closer to the number 5 than 'b' is
bool DistFrom5(int a, int b){ return std::abs(a - 5) < std::abs(b - 5); }

int main() {
    std::vector<int> foo = {5, 3, 10, 1, 7};
    std::sort(foo.begin(), foo.end(), DistFrom5);
    for(int &x : foo) std::cout << x << " ";
}

5 3 7 1 10

Great, although this is more commonly done using lambda functions which can be defined inside the call to sort().

#include <iostream>   // std::cout
#include <algorithm>  // std::sort
#include <vector>     // std::vector
#include <cmath>      // std::abs

int main() {
    
    // Make values
    std::vector<int> foo = {5, 3, 10, 1, 7};
    
    // Sort using a lambda function
    std::sort(foo.begin(), foo.end(),
              [](int a, int b) { return std::abs(a - 5) < std::abs(b - 5); });
    
    // Print result
    for(int &x : foo) std::cout << x << " ";
}

5 3 7 1 10

Stable Sort

You may have noticed this tidbit in the documentation for sort().

The order of equal elements is not guaranteed to be preserved.

This is saying that the underlying implementation of sort() is (possibly) an unstable sorting algorithm. In sorting the vector {5, 3, 10, 1, 7} by “elements closest to 5”, the result could have 3 before 7 or 7 before 3 and both would be acceptable. Sometimes this behavior is undesireable; we want to retain the original order of equivalent elements. This is known as stable sorting, and if you want to do it in C++ use stable_sort(). The drawback to using stable_sort() is that the runtime may be worse than sort().