Быстрая сортировка (merge / quick)

Быстрая сортировка (merge / quick): как это работает?

Обе сортировки режут одну задачу на две поменьше. Разница в том, где проходит разрез.

Merge режет посередине, не глядя на значения. Каждая половина сортируется тем же способом.

Слияние двух отсортированных половин это один линейный проход. Берите тот передний элемент, что меньше.

Quick выбирает опорное значение и разбивает массив вокруг него. Меньшие уходят влево, большие вправо.

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

Обе делают log n уровней работы над n элементами. Плохая опора превращает quick в O(n в квадрате).

1. [3, 1, 4, 2]Сортировка слиянием. Режем посередине, не глядя на значения.
2. [3, 1] и [4, 2]Каждую половину режем снова, до одиночных элементов.
3. [1, 3] и [2, 4]Один элемент уже отсортирован. Каждая пара сливается за одно сравнение.
4. [1, 2, ...]Слияние сравнивает два передних элемента. Единица меньше двойки и идёт первой.
5. [1, 2, 3, 4]Последнее слияние это один проход по четырём элементам. Всего два уровня.

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = arr.length >> 1;
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    const out = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
        out.push(left[i] <= right[j] ? left[i++] : right[j++]);
    }
    return out.concat(left.slice(i), right.slice(j));
}

Быстрая сортировка (merge / quick): разбор примера

K-е по величине значение

Верните k-е по величине значение в неотсортированном массиве.

Полная сортировка сработает, но сделает гораздо больше, чем спросили.

Разбейте массив вокруг опорного значения, как это делает quick sort.

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

function findKthLargest(nums, k) {
    const target = nums.length - k; // the slot it would hold once sorted
    let lo = 0;
    let hi = nums.length - 1;

    while (lo < hi) {
        const pivot = nums[hi];
        let split = lo;

        for (let i = lo; i < hi; i++) {
            if (nums[i] < pivot) {
                [nums[i], nums[split]] = [nums[split], nums[i]];
                split++;
            }
        }
        [nums[split], nums[hi]] = [nums[hi], nums[split]];

        // the pivot is final, and only one side can hold the answer
        if (split === target) return nums[split];
        if (split < target) lo = split + 1;
        else hi = split - 1;
    }

    return nums[lo];
}

Быстрая сортировка (merge / quick): когда применять?

Эти формулировки в условии ведут сюда:

• •сортировка массива реального размера (тысячи+)
• •нужна гарантированная или ожидаемая O(n log n)
• •сортировка как подготовительный шаг перед другим алгоритмом (два указателя, жадный, сканирующая прямая)
• •нужна стабильность (сортировка слиянием) или сортировка на месте (быстрая сортировка)
• •просто «отсортируй это» без намёка на малое n или особые ключи

Быстрая сортировка (merge / quick): с чем путают?

• Элементарные сортировки (выбором, пузырьком, вставками) (Elementary sorts (selection, bubble, insertion)): Те ничего не делят и стоят n в квадрате. Именно деление и покупает log n.
• Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix)): Подсчёт и разряды обгоняют n log n, читая цифры. Им нужны ключи в узком диапазоне.
• Бинарная куча / очередь с приоритетом (Binary heap / priority queue): Пирамидальная сортировка тоже n log n и без буфера. На практике она медленнее на реальных данных.
• Рекурсия (Recursion): Рекурсия это механизм, а не сам приём. Главное здесь, где проходит разрез.

Быстрая сортировка (merge / quick): частые ошибки

• Всегда берут первый элемент опорным

  Тогда отсортированный вход делится на один и n минус один. Берите случайный или средний элемент.

• При равенстве берут элемент справа

  Взятие правого при равенстве переставляет равные ключи. При совпадении берите левую половину.

• Спускаются в обе стороны при quickselect

  Нужную позицию может содержать только одна сторона. Обход обеих стоит полной сортировки.

• Забывают про буфер сортировки слиянием

  Она выделяет второй массив размером со вход. На очень больших массивах это заметно.

Быстрая сортировка (merge / quick): задачи с собеседований

• Отсортировать массив: Чистая форма, обычно это сортировка слиянием.
• K-й по величине элемент: Одно разбиение за раунд вместо полной сортировки.
• Слияние отсортированных массивов: Половина слияния из merge sort сама по себе.
• Сколько меньших справа: Подсчёт идёт прямо во время слияния.
• Обратные пары: Тот же подсчёт, но с другим сравнением.
• Сортировка связного списка: Сортировка слиянием по узлам, без буфера.
• Волнообразная сортировка II: Quickselect находит медиану, вокруг неё расставляются значения.

Быстрая сортировка (merge / quick): сложность по времени и памяти

O(n log n)

n до 1e6 даёт O(n log n). Merge требует O(n) дополнительной памяти, quick требует O(log n).