Алгоритмы

Сортировки

Семь способов упорядочить массив. Сравнение — по числу сравнений и перемещений.

  1. Пузырьковая
  2. Вставками
  3. Выбором
  4. Слиянием
  5. Быстрая
  6. Пирамидальная
  7. Подсчётом

Пузырьковая сортировка

время 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;
}