Sorting

Sorting puts the elements of an array in order: numbers from smallest to largest, names from A to Z, or by any rule you choose, such as "higher score first, equal scores by name". It is useful in many places: once an array is sorted, finding the two closest numbers, counting the different values or searching for a value becomes quick. Common sorting algorithms are bubble sort, insertion sort, merge sort, quicksort and counting sort.

Explanation

The simple ways to sort are slow. Bubble sort walks along the array and swaps every two neighbours that are out of order. One pass over 7, 2, 9, 4, 2 gives 2, 7, 4, 2, 9: the largest number has moved to the end. Each pass puts one more number in its place, so $n$ numbers need up to $n$ passes of up to $n$ comparisons, O(n^2) time. Insertion sort takes the elements one at a time and puts each into its place among the ones already sorted, also O(n^2).

The fast ways split the work. Merge sort cuts the array in half, sorts each half the same way, and then merges the two sorted halves in one pass, always taking the smaller of the two front elements. The halving goes \log_2 n levels deep, and each level does about $n$ steps of merging, so the time is O(n \log n). Quicksort picks one element, moves the smaller elements to its left and the larger ones to its right, and then sorts the two parts the same way. It is O(n \log n) on average and usually the fastest in practice. For n = 10^6, n \log_2 n is about 2 \cdot 10^7 steps, while n^2 is 10^{12}.

All of these only ever compare two elements and decide which goes first. That is what lets the same algorithm sort by any rule.

Implementation

In most programs you don't write a sort yourself: the standard library has one. sort(a.begin(), a.end()) from <algorithm> puts a vector in increasing order, so 7, 2, 9, 4, 2 becomes 2, 2, 4, 7, 9. a.begin() is the position of the first element and a.end() the position just past the last. std::sort is a quicksort that switches to another method when the parts come out badly uneven, so it is O(n \log n) on every input.

vector<int> a = {7, 2, 9, 4, 2};
sort(a.begin(), a.end());   // 2 2 4 7 9

It works for numbers and for strings. Strings compare like words in a dictionary, letter by letter, but every capital letter comes before every small letter, so "Zed" comes before "ann".

For decreasing order, pass a third argument, greater<int>(), a ready-made comparator that puts larger numbers first:

sort(a.begin(), a.end(), greater<int>());

Your own order: the comparator

A sorting algorithm needs only one question about any two elements: must a go before b? Often the rule is more than "smaller first". An olympiad results list goes from the highest score down, and pupils with equal scores go from A to Z. The function that answers the question is the comparator. This one checks the score first, the main key: if the scores differ, the higher one goes before. Only if they are equal does it compare the names, the tie-break.

Kim 7, Ann 5, Max 9, Bob 7, Eve 5 and Dan 7 come out as Max 9, Bob 7, Dan 7, Kim 7, Ann 5, Eve 5.

Sorting twice, first by score and then by name, does not work: the last sort decides the order, so the list ends up by name only, with Max last. Put both keys in one comparator (or see Two keys with stable_sort).

A pupil is a record with a name and a score. A struct groups the two fields under one type:

struct Pupil {
    string name;
    int score;
};

The comparator is a function before(a, b) that returns true if a must go before b, and false otherwise. sort takes it as its third argument.

The program has three steps:

1. Read: read the pupils into a vector.

2. Sort: one call to sort with the comparator.

3. Scan: one pass over the sorted vector, here to print it.

The input is n, then n lines with a name (one word) and a score. For the olympiad results it is:

6
Kim 7
Ann 5
Max 9
Bob 7
Eve 5
Dan 7

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Pupil {
    string name;
    int score;
};

// must a go before b?
bool before(const Pupil& a, const Pupil& b) {
    // main key
    if (a.score != b.score) return a.score > b.score;
    // tie-break
    return a.name < b.name;
}

int main() {
    // read
    int n;
    cin >> n;
    vector<Pupil> p(n);
    for (int i = 0; i < n; i++) cin >> p[i].name >> p[i].score;

    // sort
    sort(p.begin(), p.end(), before);

    // scan
    for (int i = 0; i < n; i++) cout << p[i].name << ' ' << p[i].score << '\n';
}

The parameters are const Pupil&: the & passes the original pupil instead of a copy, so sort doesn't copy a name at every comparison. The comparator can also be written in place as a lambda, a function without a name: sort(p.begin(), p.end(), [](const Pupil& a, const Pupil& b) { ... }); with the same body as before.

sort makes about n \log_2 n comparisons, so the program runs in O(n \log n) time. A comparison of two strings costs up to their length, so sorting strings of length up to $L$ takes O(L \cdot n \log n).

A pair holds two values, first and second. Two pairs compare by first, and only if those are equal, by second: the main key and the tie-break are built in.

Two keys with stable_sort

Two sorts in a row fail because the last sort decides the order, and it was the sort by the tie-break. Run them the other way round: names first, then scores. Now the second sort must leave equal scores in the order the names gave them. A sort is stable if elements with equal keys keep their current order. sort is not stable, but stable_sort from the same header is, and it also runs in O(n \log n).

// sort by the tie-break
sort(p.begin(), p.end(), [](const Pupil& a, const Pupil& b) {
    return a.name < b.name;
});
// stable_sort by the main key
stable_sort(p.begin(), p.end(), [](const Pupil& a, const Pupil& b) {
    return a.score > b.score;
});

Fig. 1. Left, after the sort by name; right, after stable_sort by score. stable_sort keeps equal scores in the order the sort by name left them.

With three keys, sort by the last tie-break, then stable_sort by the middle one, then by the main key. One comparator with all the keys needs one sort instead of one per key.

Examples of use

Many problems become easy in three steps: read the data, sort it, then scan it once from left to right. Only the scan differs from problem to problem.

Closest two numbers

Which two of the numbers 15, 3, 11, 8, 20, 6 are closest to each other? Six numbers make 15 pairs. After sorting, the numbers read 3, 6, 8, 11, 15, 20, and the closest two must stand next to each other: a number between them would be closer to each of them. So the scan compares each number only with its left neighbour, 5 pairs in all. The gaps are 3, 2, 3, 4 and 5, so the answer is 2, for 6 and 8.

Fig. 2. The sorted numbers, with the gap to the number before each one below it. The closest two numbers are neighbours in sorted order.

The input is n (n \ge 2), then the n numbers. The difference of two numbers up to 10^9 in size can exceed the range of int, so the program uses long long:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // read
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // sort
    sort(a.begin(), a.end());

    // scan
    long long best = a[1] - a[0];
    for (int i = 1; i < n; i++) best = min(best, a[i] - a[i - 1]);
    cout << best << '\n';
}

For the input 6 and 15 3 11 8 20 6 it prints 2.

Different values

How many different numbers are there among 4, 2, 7, 2, 4, 4? Sorted, they read 2, 2, 4, 4, 4, 7, and equal numbers stand in one block. The scan counts the places where a number differs from the one before it, since a new block starts there. That happens 3 times, so there are 3 different numbers.

Fig. 3. A new block starts where a value differs from the one before it: 3 starts, 3 different numbers.

In code, after the same read and sort steps:

    // scan
    int groups = 0;
    for (int i = 0; i < n; i++)
        if (i == 0 || a[i] != a[i - 1]) groups++;

Events in time order

Three guests are at a party. The first stays from hour 1 to hour 5, the second from 3 to 5, the third from 5 to 8. A guest who leaves at 5 is gone before one who arrives at 5. What is the largest number of guests present at once?

Each arrival and each departure is an event at some time. Sort the events by time, then scan them and keep a count: add 1 when a guest arrives, take 1 away when a guest leaves. The largest count is the answer, here 2.

Fig. 4. The events in time order: the time on top, the change in the middle and the count after it at the bottom. At equal times, leaving is handled before arriving.

Time 5 has three events, and their order matters. So the events need a tie-break, just like the pupils with equal scores: at equal times, leaving goes before arriving.

For the events, the input is n, then n lines with the arrival and departure times of a guest. Store each event as the pair (time, change), with change +1 for arriving and -1 for leaving. Since -1 < +1, a plain sort on pairs already puts leaving before arriving at equal times:

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    // read
    int n;
    cin >> n;
    vector<pair<int, int>> ev;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        ev.push_back(make_pair(l, +1));  // arrives
        ev.push_back(make_pair(r, -1));  // leaves
    }

    // sort
    sort(ev.begin(), ev.end());

    // scan
    int now = 0, best = 0;
    for (int i = 0; i < (int)ev.size(); i++) {
        now += ev[i].second;
        best = max(best, now);
    }
    cout << best << '\n';
}

For the party, with the input 3, 1 5, 3 5, 5 8, it prints 2. If a guest who leaves at 5 should still meet one who arrives at 5, store each departure at time r + 1 instead of r (the times are whole numbers). On the same input the answer becomes 3.

Common mistakes

• Sorting twice in the order of the rule: first by score, then by name. Use one comparator, or stable_sort in reverse order.

• Expecting sort to keep equal elements in their order, for example sorting by name and then with sort by score; small tests often hide it. Use stable_sort, or put the name into the comparator.

• Writing <= because equal elements may go either way. For two equal elements the comparator must return false, or sort can run past the end of the array; use < and >, never <= and >=.

• Joining the keys with ||, as in a.score > b.score || a.name < b.name, which compares the names even when the scores differ. Compare the tie-break only when the main keys are equal.

• Sorting the wrong range of an array numbered from 1: with the data in a[1] to a[n], sort(a, a + n) takes in the unused a[0] and leaves a[n] out. Use sort(a + 1, a + n + 1).

Similar algorithms

Counting sort works when the values are small integers, such as marks from 0 to 100. It counts how many times each value occurs instead of comparing elements, in O(n + k) for values from 0 to $k$.

A priority queue gives the smallest element of a set that keeps changing. If all the elements are known up front and don't change, sort them once.

Binary search needs a sorted array. Sort once, then answer many questions such as "is $x$ there?" or "how many elements are at most $x$?" in O(\log n) each.

Two pointers scan a sorted array with two indices at once, for example to find pairs with a given sum or difference.

A set or map also groups equal values and counts the different ones while values arrive one by one.

Many greedy algorithms start by sorting, by end time or by size. Kruskal's algorithm starts by sorting the roads by cost.

Practice