Sort a vector in C++

This post will discuss how to sort a vector of integers in C++ in ascending order.

The recommended approach is to use the standard algorithm std::sort defined in the <algorithm> header. It is usually implemented using a hybrid algorithm like Introsort, which combines quicksort with heapsort and insertion sort and produces an unstable sort, i.e., the relative order of elements with equal values is not preserved.

It has two overloaded versions:

1. The first version just takes the iterators to the initial and final positions of the vector and sorts the elements in increasing order using std::less, which will delegate to operator<.

#include <iostream>

#include <vector>

#include <algorithm>

int main()

{

std::vector<int> v = { 3, 5, 2, 4, 7 };

std::sort(v.begin(), v.end());

for (const auto &i: v) {

std::cout << i << ' ';

}

return 0;

}

Download Run Code

Output:

2 3 4 5 7

2. The second version takes a comparator to define the ordering of elements. The comparator is a binary predicate that compares its two arguments and returns a boolean value that determines whether the first argument goes before the second argument in the sorted sequence.

The two-arg version of std::sort uses the default value of std::less for the optional third argument. The following code passes std::less function object in std::sort as a comparator, which returns true if the first argument is less than the second argument. With C++14, we can even skip the template arguments. So, std::less<int>() becomes std::less<>().

#include <iostream>

#include <vector>

#include <algorithm>

int main()

{

std::vector<int> v = { 3, 5, 2, 4, 7 };

std::sort(v.begin(), v.end(), std::less<int>());

for (const auto &i: v) {

std::cout << i << ' ';

}

return 0;

}

Download Run Code

We can also pass our own function object to the std::sort function. We just need an instance of a class with operator() defined.

#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;

}

};

int main()

{

std::vector<int> v = { 3, 5, 2, 4, 7 };

std::sort(v.begin(), v.end(), comp());

for (const auto &i: v) {

std::cout << i << ' ';

}

return 0;

}

Download Run Code

The third argument can be a simple binary function, as shown below:

#include <iostream>

#include <vector>

#include <algorithm>

bool comp(int i, int j) {

return i < j;

}

int main()

{

std::vector<int> v = { 3, 5, 2, 4, 7 };

std::sort(v.begin(), v.end(), comp);

for (const auto &i: v) {

std::cout << i << ' ';

}

return 0;

}

Download Run Code

With C++11, we can even pass a lambda to the std::sort function to define the ordering.

#include <iostream>

#include <vector>

#include <algorithm>

int main()

{

std::vector<int> v = { 3, 5, 2, 4, 7 };

std::sort(v.begin(), v.end(),

[](const int &l, const int &r) {

return l < r;

});

for (const auto &i: v) {

std::cout << i << ' ';

}

return 0;

}

Download Run Code

That’s all about sorting a vector in C++.

Notes:

1. To get a stable sort, consider using std::stable_sort, which is like std::sort but maintains the relative order of equal elements.

2. We can also write our own efficient routine for sorting the vector using quicksort, mergesort algorithms, etc.

3. With C++11, we can use std::is_sorted to check if a vector is sorted or not. It is defined in the header <algorithm>.

Share this: