Сортировки
Семь способов упорядочить массив. Сравнение — по числу сравнений и перемещений.
- Пузырьковая
- Вставками
- Выбором
- Слиянием
- Быстрая
- Пирамидальная
- Подсчётом
Пузырьковая сортировка
время O(n²)
память O(1)
устойчивая
Проходим массив слева направо и меняем местами соседние элементы, если левый больше правого.
После прохода максимум оказывается в конце. Следующий проход короче на один элемент.
Если за проход не было обменов, массив уже упорядочен.
Почему верно.
Индукция по числу проходов. После k проходов последние k позиций
содержат k наибольших элементов в порядке возрастания: каждый из них
«всплывает» вправо, пока не упрётся в уже поставленный больший элемент.
Равные соседи не меняются, поэтому относительный порядок равных ключей сохраняется.
void bubble_sort(vector<int>& a) {
int n = a.size();
for (int pass = 0; pass < n; ++pass) {
bool swapped = false;
for (int i = 1; i < n - pass; ++i) {
if (a[i - 1] > a[i]) {
swap(a[i - 1], a[i]);
swapped = true;
}
}
if (!swapped) break;
}
}
Сортировка вставками
время O(n²), лучше O(n)
память O(1)
устойчивая
Префикс a[0..i) уже отсортирован. Элемент a[i] сдвигаем влево,
пока слева стоит строго больший ключ. На почти упорядоченных данных сдвигов мало,
поэтому алгоритм линеен, если массив уже отсортирован.
Почему верно.
База: один элемент упорядочен. Шаг: вставка в отсортированный префикс ставит ключ
между меньшими или равными слева и большими справа. Равные ключи не перескакиваем
(сравнение строгое), поэтому сортировка устойчива.
void insertion_sort(vector<int>& a) {
for (int i = 1; i < (int)a.size(); ++i) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
--j;
}
a[j + 1] = key;
}
}
Сортировка выбором
время O(n²)
память O(1)
неустойчивая
На шаге i ищем минимум на отрезке [i, n) и меняем его с a[i].
Число сравнений всегда около n²/2, обменов — не больше n.
Обмен может переставить равный ключ через другой такой же, поэтому устойчивость не гарантируется.
Почему верно.
После i шагов префикс a[0..i) содержит i наименьших элементов
в возрастающем порядке: каждый новый минимум не меньше уже поставленных и не больше оставшихся.
void selection_sort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n; ++i) {
int best = i;
for (int j = i + 1; j < n; ++j)
if (a[j] < a[best]) best = j;
swap(a[i], a[best]);
}
}
Сортировка слиянием
время O(n log n)
память O(n)
устойчивая
Делим массив пополам, сортируем половины рекурсивно и сливаем два упорядоченных куска.
На каждом уровне рекурсии суммарно обрабатываем n элементов, уровней log n.
Почему верно.
Слияние двух отсортированных последовательностей берёт меньший из текущих голов.
Если головы равны, берём левую — так сохраняется исходный порядок.
Индукция по длине: обе половины верны, слияние выдаёт неубывающую последовательность из всех их элементов.
void merge_sort(vector<int>& a, int l, int r, vector<int>& buf) {
if (r - l <= 1) return;
int m = (l + r) / 2;
merge_sort(a, l, m, buf);
merge_sort(a, m, r, buf);
int i = l, j = m, k = l;
while (i < m || j < r) {
if (j == r || (i < m && a[i] <= a[j])) buf[k++] = a[i++];
else buf[k++] = a[j++];
}
for (int t = l; t < r; ++t) a[t] = buf[t];
}
Быстрая сортировка
среднее O(n log n)
худшее O(n²)
память O(log n) стек
неустойчивая
Выбираем опорный элемент и раскладываем массив: слева не больше опоры, справа не меньше.
Затем сортируем части отдельно. Если разбиение каждый раз примерно пополам, глубина log n
и суммарная работа O(n log n). На уже отсортированном массиве при опоре «крайний элемент»
получается квадрат — поэтому опору лучше брать случайно или медианой из трёх.
Почему верно.
После разбиения опора стоит на своём итоговом месте: слева все ≤, справа все ≥.
Рекурсия сортирует независимые отрезки. Обмены внутри разбиения не смотрят на исходный порядок равных ключей.
int partition(vector<int>& a, int l, int r) {
int pivot = a[r - 1];
int i = l;
for (int j = l; j < r - 1; ++j) {
if (a[j] <= pivot) swap(a[i++], a[j]);
}
swap(a[i], a[r - 1]);
return i;
}
void quick_sort(vector<int>& a, int l, int r) {
if (r - l <= 1) return;
int p = partition(a, l, r);
quick_sort(a, l, p);
quick_sort(a, p + 1, r);
}
Пирамидальная сортировка
время O(n log n)
память O(1)
неустойчивая
Строим двоичную кучу на том же массиве: родитель не меньше детей.
Корень — максимум. Меняем его с последним элементом, уменьшаем кучу и восстанавливаем свойство.
Построение кучи снизу занимает O(n), каждое из n извлечений — O(log n).
Почему верно.
sift_down чинит поддерево, если дети уже кучи: больший ребёнок поднимается, пока порядок не восстановлен.
После извлечения максимум стоит в конце неотсортированной части и больше туда не попадает.
Инвариант: префикс длины heap_size — куча, суффикс — уже отсортированные максимумы.
void sift_down(vector<int>& a, int n, int i) {
while (true) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < n && a[left] > a[largest]) largest = left;
if (right < n && a[right] > a[largest]) largest = right;
if (largest == i) break;
swap(a[i], a[largest]);
i = largest;
}
}
void heap_sort(vector<int>& a) {
int n = a.size();
for (int i = n / 2 - 1; i >= 0; --i) sift_down(a, n, i);
for (int end = n - 1; end > 0; --end) {
swap(a[0], a[end]);
sift_down(a, end, 0);
}
}
Сортировка подсчётом
время O(n + k)
память O(n + k)
устойчивая
Ключи — целые числа из диапазона 0 .. k-1. Считаем, сколько раз встречается каждое значение,
затем превращаем частоты в границы: pos[x] — индекс, куда поставить следующее x.
Идём по исходному массиву слева направо и кладём элементы в новые позиции. Сравнений нет вообще.
Почему верно.
После префиксных сумм pos[x] указывает на начало блока значений x,
а pos[x+1] — на конец. Блоки идут по возрастанию ключа.
Одинаковые ключи занимают соседние ячейки в порядке обхода исходного массива, поэтому сортировка устойчива.
vector<int> counting_sort(const vector<int>& a, int k) {
vector<int> cnt(k), pos(k), out(a.size());
for (int x : a) ++cnt[x];
pos[0] = 0;
for (int x = 1; x < k; ++x) pos[x] = pos[x - 1] + cnt[x - 1];
for (int x : a) out[pos[x]++] = x;
return out;
}