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 before y. 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;
}
FunctionWhat it doesComplexity
sort(b, e)sorts in ascending orderO(n log n)
sort(b, e, greater<int>())sorts in descending orderO(n log n)
stable_sort(b, e, f)sorts and keeps the order of equal elementsO(n log n)
reverse(b, e)reverses the orderO(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 arrayO(n) on average
is_sorted(b, e)checks whether it is sortedO(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
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
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
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?