Algorithms → Sorting → Sorting in C++: the sort function and comparison
Sorting in C++: the sort Function and Comparison
Lesson 4 of 5 · Sorting
At competitions sorting is almost never written by hand – the function sort from the <algorithm> library is used. It runs in O(n log n), and with your own comparison function it sorts by any criterion: descending, by several criteria, structures, pairs and strings.
Before you start: prerequisites – simple sorting algorithms, vector in C++, structures. How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
Basic use
The function sort(begin, end) sorts in ascending order the part from begin to end (without end):
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int a[6] = {5, 2, 9, 1, 7, 3};
sort(a, a + 6); // an ordinary array: from a to a + n
for (int x : a) cout << x << " ";
cout << endl;
vector<int> v = {5, 2, 9, 1, 7, 3};
sort(v.begin(), v.end()); // a vector: from begin() to end()
for (int x : v) cout << x << " ";
cout << endl;
sort(v.begin(), v.end(), greater<int>()); // descending
for (int x : v) cout << x << " ";
cout << endl;
sort(v.begin() + 1, v.begin() + 4); // only the elements at positions 1, 2 and 3
for (int x : v) cout << x << " ";
cout << endl;
return 0;
}
A descending order is possible without greater too: sort in ascending order and then reverse the array with reverse(v.begin(), v.end()).
Your own criterion: a comparison function
With the third argument we give a function that for two elements x and y returns true if x should come beforey. For example, sorting by the sum of digits, and with an equal sum by the size of the number:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int digitSum(int x) {
int s = 0;
while (x > 0) {
s += x % 10;
x /= 10;
}
return s;
}
// true if x should come before y
bool comesFirst(int x, int y) {
if (digitSum(x) != digitSum(y)) return digitSum(x) < digitSum(y);
return x < y; // the same digit sum: the smaller number goes first
}
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int &x : v) cin >> x;
sort(v.begin(), v.end(), comesFirst);
for (int x : v) cout << x << " ";
cout << endl;
return 0;
}
Example
Input
6
19 5 23 100 41 32
Output
100 5 23 32 41 19
Important: for equal elements the comparison function must return false. If you write <= instead of <, the program may work incorrectly or crash.
Instead of a separate function, you can write a lambda – a function written at the place of the call:
sort(v.begin(), v.end(), [](int x, int y) {
return x % 10 < y % 10; // by the last digit
});
Sorting structures and pairs
The most common competition case: a ranking list. We sort the competitors by points in descending order, and those with the same number of points by name alphabetically.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Competitor {
string name;
int points;
};
bool better(const Competitor &x, const Competitor &y) {
if (x.points != y.points) return x.points > y.points; // more points go first
return x.name < y.name; // then alphabetically
}
int main() {
int n;
cin >> n;
vector<Competitor> t(n);
for (auto &x : t) cin >> x.name >> x.points;
sort(t.begin(), t.end(), better);
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << t[i].name << " " << t[i].points << endl;
return 0;
}
Example
Input
5
Mark 80
Anna 95
John 80
Ivy 70
Luke 95
Output
1. Anna 95
2. Luke 95
3. John 80
4. Mark 80
5. Ivy 70
Pairs (pair) are compared without an extra function first by first, and then by second. A trick: if we store the pair (-points, name), an ordinary sort gives the same ranking list. Pairs are also handy when the original position of an element has to be remembered:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> p(n); // (value, original position)
for (int i = 0; i < n; i++) {
cin >> p[i].first;
p[i].second = i + 1;
}
sort(p.begin(), p.end());
// the order numbers of the elements from the smallest to the largest
for (auto &x : p) cout << x.second << " ";
cout << endl;
return 0;
}
For the input 5 / 40 10 30 20 50 the program prints 2 4 3 1 5: the smallest number (10) was in the 2nd place, the next one (20) in the 4th, and so on.
Strings, stable_sort and removing duplicates
Strings are compared lexicographically (as in a dictionary, by ASCII codes: capital letters come before lowercase ones, and "ab" < "abc"), so sort on a vector of strings gives alphabetical order.
stable_sort does the same as sort, but keeps the order of equal elements. The combination sort + unique + erase removes duplicates:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {4, 1, 4, 2, 1, 4, 3};
sort(v.begin(), v.end()); // 1 1 2 3 4 4 4
v.erase(unique(v.begin(), v.end()), v.end()); // unique moves the distinct ones to the beginning
for (int x : v) cout << x << " ";
cout << endl;
cout << "Distinct values: " << v.size() << endl;
return 0;
}
Function
What it does
Complexity
sort(b, e)
sorts in ascending order
O(n log n)
sort(b, e, greater<int>())
sorts in descending order
O(n log n)
stable_sort(b, e, f)
sorts and keeps the order of equal elements
O(n log n)
reverse(b, e)
reverses the order
O(n)
unique(b, e)
removes consecutive duplicates (sort before it)
O(n)
nth_element(b, b + k, e)
puts at the place k the element that would be there in the sorted array
O(n) on average
is_sorted(b, e)
checks whether it is sorted
O(n)
Practice tasks
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
TASK 01Difficulty: medium
A ranking list with shared places
Competitors are given (a name and points). Print the ranking list sorted by points in descending order, and with equal points by name. Competitors with the same number of points share the same place, and the next place is skipped (for example 1, 2, 2, 4).
Example
Input
5
Mark 80
Anna 95
John 80
Ivy 70
Luke 95
Output
1. Anna 95
1. Luke 95
3. John 80
3. Mark 80
5. Ivy 70
Hint
After sorting, the place of the competitor at position i is i + 1, unless they have the same points as the previous one – then they get the same place as that competitor.
Solution (C++)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Competitor {
string name;
int points;
};
int main() {
int n;
cin >> n;
vector<Competitor> t(n);
for (auto &x : t) cin >> x.name >> x.points;
sort(t.begin(), t.end(), [](const Competitor &x, const Competitor &y) {
if (x.points != y.points) return x.points > y.points;
return x.name < y.name;
});
int place = 1;
for (int i = 0; i < n; i++) {
if (i > 0 && t[i].points != t[i - 1].points) place = i + 1;
cout << place << ". " << t[i].name << " " << t[i].points << endl;
}
return 0;
}
TASK 02Difficulty: easy
Even first, then odd
Sort n natural numbers so that first come all the even numbers in ascending order, and then all the odd ones in descending order.
Example
Input
7
5 8 3 2 9 4 1
Output
2 4 8 9 5 3 1
Hint
In the comparison function: if one number is even and the other odd, the even one goes first. If both are even – the smaller one goes first; if both are odd – the larger one goes first.
Solution (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool comesFirst(int x, int y) {
bool ex = (x % 2 == 0), ey = (y % 2 == 0);
if (ex != ey) return ex; // an even number goes before an odd one
if (ex) return x < y; // both even: ascending
return x > y; // both odd: descending
}
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int &x : v) cin >> x;
sort(v.begin(), v.end(), comesFirst);
for (int x : v) cout << x << " ";
cout << endl;
return 0;
}
TASK 03Difficulty: harder
Merging intervals
n intervals [a, b] are given (1 ≤ n ≤ 105). Intervals that overlap or touch are merged into one. Print the resulting intervals from left to right.
Example 1
Input
4
1 3
8 10
2 6
15 18
Output
1 6
8 10
15 18
Example 2
Input
2
1 4
4 5
Output
1 5
Hint
Sort the intervals by their start (pairs are sorted by first). Then go in order: if the current interval starts before the end of the last merged one (a <= end), extend the end to max(end, b); otherwise start a new interval.
Solution (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> v(n);
for (auto &p : v) cin >> p.first >> p.second;
sort(v.begin(), v.end()); // by the start of the interval
vector<pair<int, int>> merged;
for (auto &p : v) {
if (!merged.empty() && p.first <= merged.back().second)
merged.back().second = max(merged.back().second, p.second); // it overlaps: extend
else
merged.push_back(p); // a new interval
}
for (auto &p : merged) cout << p.first << " " << p.second << endl;
return 0;
}
Common mistakes and tips
For a vector you write sort(v.begin(), v.end()), and for an array sort(a, a + n) – not a + n - 1.
A comparison function uses a strict < or >, never <=.
Pass structures to the comparison function by reference (const Competitor &) – otherwise they are copied at every comparison.
unique removes only consecutive duplicates – the array must be sorted first.
Check your knowledge
Open the quiz
The sort function in C++
1. How is the whole vector v sorted in ascending order?
2. What does the comparison function comesFirst(x, y) return?
3. How are two pairs (a, b) and (c, d) compared?
4. What should be done before unique to remove all the duplicates?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.