Быстрая сортировка

Пошаговые видео

Два способа разбиения, каждый в горизонтальном и вертикальном формате. Отключаемые русские субтитры доступны на YouTube.

Опорный элемент и активный диапазон

Рамка показывает диапазон [start, end): правая граница не включается. Фиолетовый p — последний элемент, выбранный опорным. Жёлтый j перебирает остальные значения, голубой i указывает следующую позицию для значения меньше опорного.

Начальный пример содержит десять элементов и повторы. Буквы различают равные значения, поэтому можно увидеть изменение их порядка.

Инвариант разбиения Ломуто

Перед каждой проверкой [start, i) содержит значения строго меньше опорного; [i, j) — уже проверенные значения, не меньшие опорного; [j, end − 1) ещё не проверен. Сам опорный пока стоит в end − 1.

Если a[j] < pivot, меняем a[i] и a[j] и сдвигаем i. Затем переходим к следующему j. В конце переносим опорный на i: слева все значения меньше, справа — не меньше. Опорный уже занимает окончательную позицию, но обе части ещё нужно отсортировать.

Почему сортировка нестабильна

Попробуйте [2, 2]. Опорный — 2b. Значение 2a не меньше опорного, поэтому граница i остаётся в начале. Финальный обмен даёт [2b, 2a]: значения отсортированы, но исходный порядок двоек нарушен.

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

Время, память и счётчики

При сбалансированных разбиениях время Θ(n log n). В среднем по случайным перестановкам различных значений — Θ(n log n), но фиксированный последний опорный не даёт гарантии. На возрастающем, убывающем и полностью равном массиве эта версия делает n(n − 1)/2 сравнений и работает за Θ(n²).

Разбиение выполняется на месте. Стек прямой рекурсии занимает O(log n) при сбалансированных разбиениях и O(n) в худшем случае. Обёртка копирует вход за O(n) памяти. Для визуализации отдельно сохраняются снимки: до O(n²) шагов по O(n) данных, то есть до O(n³) памяти. Поэтому ввод ограничен 24 элементами.

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

Реализация на JavaScript

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

function quickSort(values) {
    const result = [...values];
    function sort(start, end) {
        if (end - start < 2) return;
        const pivot = result[end - 1];
        let boundary = start;
        for (let scan = start; scan < end - 1; scan++) {
            if (result[scan] < pivot) {
                [result[boundary], result[scan]] = [result[scan], result[boundary]];
                boundary++;
            }
        }
        [result[boundary], result[end - 1]] = [result[end - 1], result[boundary]];
        sort(start, boundary);
        sort(boundary + 1, end);
    }
    sort(0, result.length);
    return result;
}

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

Слияние гарантирует Θ(n log n) и сохраняет порядок равных элементов, но использует буфер. Quick sort этой реализации может ухудшиться до Θ(n²) и нестабилен. Случайный выбор опорного уменьшает зависимость от порядка входа, но сам по себе не устраняет плохое поведение двухстороннего разбиения на полностью равных значениях.

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

Что проверить самостоятельно

Сравните исходный массив с возрастающим, убывающим и массивом одинаковых значений. Посчитайте сравнения, проследите границы i и j. Затем введите [2, 2], чтобы увидеть нестабильность. Пустой и одиночный массив не требуют сравнений или обменов.

Трёхстороннее разбиение: меньше, равно, больше

Переключите плеер на «Трёхстороннее» и нажмите «Пример с повторами» или «Все равны». Оба варианта выбирают значение последнего элемента активного диапазона; трёхсторонний сохраняет его отдельно до любых обменов. Опорный элемент может перемещаться, опорное значение не меняется.

Инвариант перед проверкой: [start, lt) < pivot; [lt, i) = pivot; [i, gt) ещё не просмотрен; [gt, end) > pivot. Для меньшего значения меняем a[lt] и a[i], затем сдвигаем обе границы. Для большего уменьшаем gt и меняем a[i] с a[gt], не сдвигая i: пришедшее справа значение ещё не проверено. Для равного только увеличиваем i.

Когда i = gt, непроверенная часть пуста. Вся равная полоса [lt, gt) стоит окончательно, и рекурсия обрабатывает только меньшую и большую части. На n ≥ 2 одинаковых элементах — 2n проверок (<, затем > для каждого элемента), ноль обменов и одно разбиение. У Ломуто — n(n − 1)/2 сравнений. Меньше проверок на любом входе не гарантируется: для 2 или 3 одинаковых элементов Ломуто делает их меньше, хотя его рост квадратичный.

Среднее время на случайных перестановках различных значений — Θ(n log n), худшее при неудачных опорных остаётся Θ(n²). Стек рекурсии и затраты истории рассматриваются отдельно, как у Ломуто. Алгоритм остаётся нестабильным: на [2, 2, 1] равные двойки меняют исходный порядок.

function threeWayQuickSort(values) {
    const result = [...values];
    function sort(start, end) {
        if (end - start < 2) return;
        const pivot = result[end - 1];
        let less = start, scan = start, greater = end;
        while (scan < greater) {
            if (result[scan] < pivot) {
                [result[less], result[scan]] = [result[scan], result[less]];
                less++;
                scan++;
            } else if (result[scan] > pivot) {
                greater--;
                [result[scan], result[greater]] = [result[greater], result[scan]];
                // Recheck the incoming item; do not advance scan.
            } else {
                scan++;
            }
        }
        sort(start, less);
        sort(greater, end);
    }
    sort(0, result.length);
    return result;
}