Вступление

Сортировка - одна из самых распространённых подзадач, часто встречающаяся в задачах всех уровней сложности. Существует множество алгоритмов, решающих её - алгоритмов сортировки. В стандартных библиотеках большинства современных языков программирования уже содержится эффективный алгоритм сортировки, и при решении задач вам вряд ли придётся реализовывать свой самостоятельно. Несмотря на это, полезно знать принцип работы и сложность различных алгоритмов, и уметь реализовывать хотя бы один эффективный алгоритм “на всякий случай”.

Постановка задачи

Простым примером сортировки является упорядочивание набора чисел по убыванию или возрастанию. Точное определение сортировки более обобщено: сортировка упорядочивает заданный набор объектов согласно заданному отношению между ними. Например, объектами могут быть числа, строки, точки в пространстве, а отношением - операция сравнения целых объектов или их отдельных частей (например точки на плоскости можно сортировать по любой из их координат).

Сортировка вставками (Сложность: \(O(N^2)\))

Один из самых простых алгоритмов сортировки - сортировка вставками (англ. insertion sort). Его идея заключается в поддерживании в левой части массива отсортированного отрезка и постепенном его расширении вправо за счёт перемещения очередного соседнего элемента в соответствующую ему позицию.

В качестве иллюстрации можно посмотреть видео:

Легко заметить, что сложность этого алгоритма - \(O(N^2)\): в худшем случае (массив упорядочен наоборот) потребуется \(i\) замен для перемещения элемента с индексом \(i\) на своё место (крайнее левое). Для всего алгоритма потребуется \(\sum_{i=1}^{N} i \in O(N^2)\) замен.

Реализация алгоритма достаточно прямолинейна:

1
2
3
4
5
6
7
8
9

void insertion_sort(vector<int>& v) {
    for (int i = 0; i < v.size(); i++) {
        int cur = i;
        while (cur > 0 && v[cur - 1] > v[cur]) {
            swap(v[cur - 1], v[cur]);
            cur--;
        }
    }
}

Сортировка слиянием (Сложность: \(O(N \log N)\))

Можно доказать, что не существует алгоритма сортировки, основанного на сравнениях, сложность которого меньше \(O(N \log N)\). Поэтому каждый алгоритм сравнения с такой сложностью можно назвать “оптимальным”.

Существует множество различных оптимальных алгоритмов сортировки, у каждого из которых есть свои плюсы и минусы. Более подробно к этому мы ещё вернёмся позже, но пока что перечислим самые распространённые из оптимальных алгоритмов:

  • Пирамидальная сортировка (англ. heapsort)
  • Сортировка слиянием (англ. merge sort)
  • Быстрая сортировка (англ. quicksort)

Все они не настолько банальны как квадратичные алгоритмы, и требуют дополнительных знаний для анализа. Наверное, проще всего проанализировать сортировку слиянием.

Идея сортировки слиянием заключается в следующем: допустим мы знаем, что массив можно разбить на две примерно равные части, и каждая из них уже будет отсортирована. Нам нужно лишь “слить” эти две части, и мы получим отсортированный массив.

Для слияния мы создаём новый массив, изначально пустой. Затем мы параллельно идём по двум частям изначального массива, поддерживая два указателя, и на каждой итерации добавляем в новый массив меньший элемент из двух текущих, сдвигая вперёд соответствующий указатель. После добавления всех элементов из двух сливаемых частей содержание нового массива копируется в изначальный массив.

Осталось лишь понять, каким образом мы можем получить массив, две части которого уже отсортированы, ведь массив на входе алгоритма - произвольный. Сортировка слиянием - классический пример рекурсивного алгоритма: он использует самого себя для сортировки частей массива. Это может быть не совсем интуитивно, но важно заметить простой факт: если на входе алгоритма массив длиной 1, то никаких операций выполнять не нужно. Вызывая самого себя рекурсивно, алгоритм всегда будет “упираться” в этот крайний случай, и поэтому он не будет работать бесконечно.

Для того, чтобы понять общую идею рекурсивных алгоритмов, лучше всего внимательно проанализировать код, приведённый ниже, или очередное иллюстративное видео:

Чтобы показать, что сложность алгоритма действительно равна \(O(N \log N)\), разобьём все “слияния”, выполненные в процессе сортировки массива на “слои”. Слияние двух частей изначального массива - первый слой, слияния частей каждой из этих двух частей (четвертей оригинального массива) - второй слой, и т.д. Заметим несколько фактов:

  1. Слияние двух частей отрезка, длина которого равна \(K\), выполняется за \(O(K)\)
  2. Сумма длин всех отрезков сортируемых слиянием на каждом слое равна \(N\)
  3. Количество слоёв равно \(\lceil \log_2 N \rceil\)

Из фактов 1 и 2 следует что на каждом слое все слияния выполняются за \(O(N)\). Используя факт 3 видим, что сложность всего алгоритма равна \(O(N \log N)\).

И наконец, реализация алгоритма:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

void merge_sort(vector<int>& v, int begin, int end) {
    // Для отрезков длиной 1 не выполняем никаких операций.
    // Это так называемый "базовый" (крайний) случай рекурсии, который
    // гарантирует, что алгоритм закончит своё выполнение.
    if (begin == end) {
        return;
    }

    int mid = (begin + end) / 2;

    // Рекурсивные вызовы алгоритма.
    merge_sort(v, begin, mid);
    merge_sort(v, mid + 1, end);

    // Собственно слияние.
    vector<int> t;
    for (int i = begin, j = mid + 1; i <= mid || j <= end;) {
        // Если одна из частей закончилась, добавляем элемент из другой
        if (i > mid) {
            t.push_back(v[j++]);
        } else if (j > end) {
            t.push_back(v[i++]);
        // Иначе добавляем меньший из текущих элементов
        } else if (v[i] <= v[j]) {
            t.push_back(v[i++]);
        } else {
            t.push_back(v[j++]);
        }
    }

    // Копируем отсортированный отрезок из временного массива в v.
    for (int i = 0; i < t.size(); i++) {
        v[begin + i] = t[i];
    }
}

Стандартные алгоритмы сортировки

Стандартная библиотека любого современного языка программирования включает в себя реализацию эффективного алгоритма сортировки. Чаще всего вместо одного канонического алгоритма используется адаптивная комбинация нескольких алгоритмов: например, одна из самых распространённых реализация стандартной библиотеки C++ (libstdc++) использует комбинацию heapsort, merge sort, и insertion sort.

// std::sort в С++ принимает два random-access итератора.
void sort(iterator first, iterator last);

Для сортировки контейнеров, предоставляющих итераторы random-access (std::vector, std::deque, и т.д.) чаще всего используются методы begin и end:

sort(v.begin(), v.end());             // весь вектор
sort(v.begin() + i, v.begin() + j);   // отрезок v[i; j)

Важно помнить, что как и все алгоритмы стандартной библиотеки, std::sort принимает, что итераторы обозначают начало включительно, а конец - не включительно.

Для сортировки “старых” массивов используется автоматическое преобразование указателя в итератор:

int a[N];
sort(a, a + N);

Сортировка сложных типов. Собственные компараторы

Иногда в задаче требуется отсортировать не числа, а некоторые сложные объекты, состоящие из нескольких элементов. Для сортировки таких объектов чаще всего нужно вручную указывать параметр, который будет сравниваться при сортировке. Для этого и предназначены компараторы.

Компаратор в C++ - логическая функция, которая принимает два объекта одинакового типа, и возвращает true, если первый из них “меньше” второго и false в противном случае. В этом контексте “меньше” значит, что в отсортированном массиве этот элемент обязательно должен стоять раньше.

Для использования собственного компаратора нам потребуется перегрузка функции std::sort, которая принимает дополнительный третий параметр - компаратор, по которому будет вестить сортировка.

Приведём простой пример. Давайте сортировать результаты команд в соревновании по правилам ACM в порядке мест. То есть, место команды выше места другой команды, если она решила больше задач, или у неё меньше штраф.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <bits/stdc++.h>

using namespace std;

struct team {
    string name;
    int tasks;      // количество решённых задач
    int penalty;    // штраф
};

// cmp(A, B) == true тогда и только тогда, когда команда
// A в таблице результатов должна оказаться выше команды B.
bool cmp(team a, team b) {
    return a.tasks > b.tasks
        || (a.tasks == b.tasks && a.penalty < b.penalty);
}

int main() {
    vector<team> teams {
        {"Team BSEU", 9, 300},
        {"Team BSU", 10, 350},
        {"Team BSUIR", 9, 200}
    };

    sort(teams.begin(), teams.end(), cmp);

    for (team t: teams) {
        cout << t.name << endl;
    }
}

Эта программа выпишет

Team BSU
Team BSUIR
Team BSEU

Важно понимать, что любой компаратор \(\prec\) по сути является математическим объектом, и должен обладать несколькими важными свойствами, большинство из которых тривиальны, кроме одного: транзитивности. Компаратор является транзитивным, если из \(a \prec b\) и \(b \prec c\) следует, что \(a \prec c\). Это может казаться очевидным, но можно легко определить функцию, которая не транзитивна, и попытаться использовать её как компаратор. Математически это не имеет смысла, практически поведение std::sort в такой ситуации не определено и может стать причиной неожиданных и странных ошибок.

В определённых случаях реализовывать свой компаратор не требуется. А именно, если для данного типа определён оператор <, то он будет использован как компаратор по умолчанию. Например, благодаря этому для сортировки чисел нам не требуется компаратор.

Стоит также отдельно упомянуть стандартный тип std::pair. Для него так же как и для чисел определён оператор < следующим образом: если первые элементы пар отличаются, то сравниваются они, иначе сравниваются вторые элементы. Другими словами, сортировка пар без компаратора происходит по возрастанию первого элемента, а при равенстве первых - по возрастанию второго.

Понятие стабильной сортировки

Иногда от сортировки нам требуется определённое свойство: она не должна менять местами “неотличимые” элементы. Это может быть важно при сортировке сложных объектов собственными компараторами, например, в предыдущем разделе при сравнении объектов team не учитывалось поле name: две команды с одинаковым результатом считались “равными” даже если их названия не совпадали.

Стабильная сортировка гарантирует, что при наличии таких объектов в изначальном массиве, их положение относительно друг друга не изменится.

Для примера рассмотрим следующий массив объектов team:

{"Team BSEU", 9, 200}
{"Team BSU", 10, 350}
{"Team BSUIR", 9, 200}

Существует два “корректных” способа их сортировки:

{"Team BSU", 10, 350}
{"Team BSEU", 9, 200}
{"Team BSUIR", 9, 200}

и

{"Team BSU", 10, 350}
{"Team BSUIR", 9, 200}
{"Team BSEU", 9, 200}

Нестабильная сортировка (например, std::sort в C++) может отсортировать массив обоими способами. При стабильной сортировке возможен только первый из них, так как относительное положение команд BSEU и BSUIR в нём сохраняется.

Стандартная библиотека C++ включает в себя оптимальную реализацию алгоритма стабильной сортировки со сложностью \(O(N \log N)\). Как и std::sort, определены две перегрузки:

void stable_sort(iterator begin, iterator end);
void stable_sort(iterator begin, iterator end, comparator comp);

Разумеется, за стабильность приходится платить другими характеристиками. Стабильная сортировка работает медленнее, чем нестабильная, хотя их сложность одинаковая: \(O(N \log N)\).

Небольшое сравнение оптимальных алгоритмов сортировки

Как мы видим, различные алгоритмы сортировки с одинаковой сложностью могут обладать разными свойствами и быть более или менее пригодными в разных ситуациях.

Кроме стабильности, другим важным свойством алгоритма сортировки является сложность по памяти: в некоторых ситуациях использование больших объёмов дополнительной памяти является неприемлемым. Алгоритмы, которые используют “мало” дополнительной памяти, называют in-place алгоритмами.

Возвращаясь к трём наиболее распространённым оптимальным алгоритмам сортировки, приведём краткий обзор их плюсов и минусов:

Алгоритм Худший случай Средний случай Память Стабильность
Heapsort \(O(N \log N)\) \(O(N \log N)\) \(O(1)\) Нет
Merge sort \(O(N \log N)\) \(O(N \log N)\) \(O(N)\) Да
Quicksort \(O(N^2)\) \(O(N \log N)\) \(O(\log N)\) Нет

Как мы видим, heapsort и merge sort гарантированно работают за \(O(N \log N)\), причём heapsort не использует дополнительной памяти, а merge sort - стабилен.

Немного парадоксально то, что quicksort для некоторых массивов может работать за \(O(N^2)\), хотя для среднего (случайно взятого) массива его время работы чаще всего меньше, чем у конкурентов, несмотря на одинаковую сложность \(O(N \log N)\).

Именно для компенсации недостатков каждого из этих алгоритмов в стандартных библиотеках большинства языков используются их адаптивные комбинации.

Алгоритмы сортировки не использующие сравнения

Все алгоритмы сортировки, описанные выше, основаны на сравнениях: единственным требованием к массиву на входе является наличие линейного порядка (компаратора) для типа элементов массива. Теоретическое ограничение сложности \(O(N \log N)\) применимо именно к таким алгоритмам.

Для некоторых специфических видов массивов существуют алгоритмы сортировки, которые работают быстрее. Рассмотрим самый распространённый из них: сортировку подсчётом.

Идея сортировки подсчётом банально проста: если элементы массива могут принимать только значения из определённого небольшого множества размера \(K\), то мы можем отсортировать массив за время \(O(N + K)\) и память \(O(K)\), просто посчитав количество элементов равных каждому возможному значению, и записав их в массив по порядку. Если \(K < N\), то сложность такого алгоритма равна \(O(N)\).

Например, пусть нам нужно отсортировать массив \(a\) из \(N \le 10^6\) чисел, причём известно, что для каждого \(a_i\), \(1 \le a_i \le 10^6\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <bits/stdc++.h>

using namespace std;

const int MAX_VALUE = 1000000;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> num_count(MAX_VALUE + 1, 0);
    for (int x: a) {
        num_count[x]++;
    }

    for (int num = 1; num <= MAX_VALUE; num++) {
        for (int i = 0; i < num_count[num]; i++) {
            cout << num << ' ';
        }
    }
    cout << endl;
}

Выигрыш в сложности между \(O(N)\) и \(O(N \log N)\) может казаться незначительным, но он гораздо более заметен, когда в программе много раз выполняется сортировка небольших массивов. Стоит помнить о сортировке подсчётом, и использовать её, когда это возможно.