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 $xxx$ is less than object $yyy$, return true
• If object $xxx$ is greater than or equal to object $yyy$, 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.