Sorting

Sorting in arrays, vectors, and other STL, as well as how to use auto comparators

Sorting

Default ways to sort in C++:

sort(v.begin(), v.end()); on vectors

sort(arr, arr + n);on arrays

By default, the sort() function sorts the elements in ascending order.

To sort in descending order:

sort(arr, arr + n, greater<int>());

The time complexity of most sorting is O(NlogN)

Custom Comparator

One often needs to apply certain types of sorting that are not provided by default by C++.

This would apply to using other C++ STLs such as set, map, priority_queue, etc, as well as custom classes.

bool cmp(const Edge &x, const Edge &y) { return x.w < y.w; }
sort(begin(v), end(v), cmp);

Or written in lambda expression:

sort(begin(v), end(v), [](const Edge &x, const Edge &y) { return x.w < y.w; });

Comparators usually compare two objects in the following way, in ascending order:

  • If object xxxxxx is less than object yyyyyy, return true

  • If object xxxxxx is greater than or equal to object yyyyyy, return false

Typical Data Structures

set<int, greater<int>> a;
map<int, string, greater<int>> b;
priority_queue<int, vector<int>, greater<int>> c;

Note: Priority queue by default is a max heap.

Last updated