Если есть множество каких-то объектов и можно однозначно сравнить один элемент с другим и сказать, что один из них меньше/больше, то можно отсортировать множество (в порядке убывания или возрастания).
Сортировка позволяет реализовывать большое количество более сложных алгоритмов.
Для простоты определим, что мы хотим сортировать по неубыванию, т.е. для любого \(i\) выполнено \(a_i \le a_{i+1} \) после сортировки.
Давайте пройдемся по массивую и если \(p_i > p_{i+1} \) поменяем их местами. Заметим, что так пройтись нам надо не больше \(n\) раз. Значит асимптотика алгоритма \(O(n^2)\). Этот алгоритм называется сортировкой пузырьком.
Давайте сначала научимся делать следующую штуку: даны два отсортированных массива \(a\) и \(b\), необходимо за \(O(n)\) научиться их сливать в один массив отсортированный массив.
Очевидно, что можно действовать следующим образом: посмотрим на первые элементы \(a\) и \(b\), выберем из них наименьший, удалим его и добавим в конец результирующего массива. Можно не удалять элементы явно, а поддерживать указатель на первый элемент. Отсюда и название техники - "два указателя".
Хорошо, теперь мы умеем из двух отсортированных массива получать один большой отсортированный массив за \(O(n)\). Давайте применим технику "разделяй и властвуй": возьмем массив, разделим его на две равные части, рекурсивно запустимся от них, получим две части, уже отсортированные, и сольем их за O(n). Дно рекурсии - случай, когда длина массива равна \(1\) - его не надо сортировать.
Докажем, что асимптотика \( O(n \log{n} )\). Расмотрим дерево рекурсии сортировки слиянием. На одном уровне рекурсии суммарно хранится примерно один массив, всего уровней \( \log{n} \), так как мы делили массив пополам. Итого, асимптотика \( O(n \log{n} ) \).
#define vi vector< int >
// сократим vector для удобства чтения
// на самом деле есть функция std::merge() которая ничуть не хуже
vi merge(vi a, vi b) {
vi ans;
int i = 0, j = 0;
while( i!=a.size() && j!=b.size() ) {
if(a[i] < b[i]) ans.push_back(a[i++]);
else ans.push_back(b[j++]);
}
// добьем оставшиеся элементы
while(i < a.size()) ans.push_back(a[i++]);
while(j < b.size()) ans.push_back(b[j++]);
return ans;
}
vi mergesort(vi a) {
if(a.size() == 1) return a; // случай n=1 тривиален
// медиана, по которой делим массив:
int med = a.size()/2;
vi a1, a2;
for(int i = 0;i < med; i++) a1.push_back(a[i]);
for(int i = med; i < a.size(); i++) a2.push_back(a[i]);
// отсортируем массивы рекурсивно и после сольем их
return merge( mergesort(a1), mergesort(a2) );
}
Давайте также рекурсивно реализуем сортировку: выберем какой-то элемент, в первой части расположим элементы меньше его, во второй - большие либо равные ему. Теперь отсортируем эти две части рекурсивно. В среднем этот алгоритм будет работать за \(O(n \log{n})\), так как части обычно будут равными, поэтому деление массива будет примерно на два.
Все алгоритмы сортировки интересны и в той же мере бесполезны. Куда более интересны идеи, применяющиеся в алгоритмах сортировок. Знание конкретной реализации не нужно, так как во всех языках есть хорошая реализация сортировки, работающая достаточно быстро. Рассмотрим std::sort - там обычно что-то сложное, но главное очень быстрое.
| \(n\) | затраченное время* |
| \(10^5\) | 0.006 мс |
| \(10^6\) | 0.065 мс |
| \(10^7\) | 0.660 мс |
*измерения проводились на codeforces на случайных тестах, можно подобрать тесты, когда время будет немногим больше
Как видим, стандартная сортировка очень и очень быстрая, константа весьма мала, и даже для \(10^7\) вполне возможно запускать подобные алгоритмы.