Sort a vector in descending order in C++
This post will discuss how to sort a vector in descending order in C++.
1. Use std::sort (or std::stable_sort)
An efficient solution is to use the std::sort algorithm defined in the <algorithm> header. It is usually a highly efficient implementation of the Introsort algorithm, which begins with quicksort and switches to heapsort when the recursion goes too deep.
The std::sort algorithm does not maintain the relative order of equal elements. To get a stable sort, go with std::stable_sort, which uses the mergesort algorithm.
The two-arg version of the std::sort algorithm sorts the vector in ascending order using operator<. To get the descending order, make a call to std::reverse after std::sort.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.begin(), vec.end()); std::reverse(vec.begin(), vec.end()); // do anything return 0; } |
The above code requires an extra pass to reverse the vector. One can avoid the call to std::reverse by using reverse iterators.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.rbegin(), vec.rend()); // do anything return 0; } |
2. Using std::sort + comparator
The std::sort function has another overloaded version that accepts a comparator. The comparator is a binary predicate that takes two arguments and returns a boolean value that determines whether the first argument appears before the second argument in the output sequence.
1. We can use std::greater as a comparator, which returns true if the first argument is more than the second argument. Starting from C++14, you can even skip the template arguments, i.e., std::greater<int>() becomes std::greater<>().
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.begin(), vec.end(), std::greater<>()); // do anything return 0; } |
2. The comparator can be a simple binary function, or you can pass your own function object. You just need an instance of a class with operator() defined.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <iostream> #include <vector> #include <algorithm> // Binary predicate struct comp { template<typename T> bool operator()(const T &l, const T &r) const { return l > r; } }; /* bool fn(int i, int j) { return i > j; } */ int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.begin(), vec.end(), comp()); // or call // std::sort(vec.begin(), vec.end(), fn); // do anything return 0; } |
3. With C++11, you can even pass a lambda function to std::sort function.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = { 7, 3, 5, 1, 9 }; std::sort(vec.begin(), vec.end(), [](const int &l, const int &r) { return l > r; }); // do anything return 0; } |
3. Custom Sorting Routine
Finally, you can also write your own efficient routine for sorting the vector in descending order using quicksort, mergesort algorithms, etc.
That’s all about sorting a vector in descending order in C++.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)