Элементарные сортировки (выбором, пузырьком, вставками)

Элементарные сортировки (выбором, пузырьком, вставками): как это работает?

Все три держат отсортированную часть и неотсортированную. Каждый раунд переносит через границу один элемент.

Сортировка выбором ищет в неотсортированной части минимум. Она меняет его местами с нужной позицией.

Пузырёк сравнивает соседние пары и меняет их при нарушении порядка. Наибольшее значение уплывает в конец.

Вставки берут следующий элемент и двигают его влево. Движение прекращается, как только сосед меньше.

Знать стоит именно вставки. На почти отсортированных данных они почти ничего не делают.

Все три работают на месте с O(1) памяти. Вставки и пузырёк устойчивы, выбор нет.

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

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        const key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

Элементарные сортировки (выбором, пузырьком, вставками): разбор примера

Сортировка вставками на связном списке

Дан односвязный список, его надо отсортировать вставками.

Перевязывать узлы можно. Копировать значения в массив нельзя.

Стройте второй, отсортированный список по одному узлу.

Для каждого узла идите по отсортированному списку с начала, пока следующее значение не станет больше. Там и вставляйте.

function insertionSortList(head) {
    const dummy = new ListNode(0);
    let node = head;

    while (node) {
        const next = node.next;

        // walk from the front each time: the sorted part has no back links
        let prev = dummy;
        while (prev.next && prev.next.val < node.val) {
            prev = prev.next;
        }

        node.next = prev.next;
        prev.next = node;
        node = next;
    }

    return dummy.next;
}

Элементарные сортировки (выбором, пузырьком, вставками): когда применять?

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

• •n маленькое (десятки или пара сотен)
• •массив уже почти отсортирован
• •сортировка на месте с O(1) дополнительной памяти
• •учебный/собеседовательный вопрос о механике сортировки
• •важна стабильность, а простота приемлема

Элементарные сортировки (выбором, пузырьком, вставками): с чем путают?

• Быстрая сортировка (merge / quick) (Fast sort (merge / quick)): Merge и quick делят массив и стоят n log n. Эти три ничего не делят.
• Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix)): Сортировка подсчётом читает значения, а не сравнивает их. Для этого нужен небольшой диапазон ключей.
• Сортировка с пользовательским компаратором (Sort with a custom comparator): Та страница про то, какой порядок вам нужен. Эта про то, как порядок получается.
• Бинарная куча / очередь с приоритетом (Binary heap / priority queue): Сортировка выбором каждый раунд ищет минимум перебором. Куча отдаёт его за log n.

Элементарные сортировки (выбором, пузырьком, вставками): частые ошибки

• По привычке берут пузырёк

  Он делает больше всех работы при том же классе сложности. Вставки лучше по умолчанию.

• Сортируют так большой вход

  При n в 1e5 квадрат это 1e10 операций. Возьмите встроенную сортировку.

• Ведут внутренний цикл до нулевого индекса

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

• Берут выбор там, где важны равные ключи

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

Элементарные сортировки (выбором, пузырьком, вставками): задачи с собеседований

• Отсортировать массив: Любой из трёх хватает при нескольких тысячах элементов.
• Сортировка вставками на списке: Тот же цикл, но по узлам, а не по ячейкам.
• Сортировка цветов: Значений всего три, поэтому один проход бьёт любую сортировку сравнением.
• Почти отсортированный массив: Вставки линейны, когда каждый элемент близко к своему месту.
• Проверка роста в шеренге: Сравните ряд с его же отсортированной копией.
• Сортировка по чётности: Это разбиение, а не полная сортировка.
• Первое пропущенное положительное: Циклическая сортировка ставит каждое значение на свой индекс.

Элементарные сортировки (выбором, пузырьком, вставками): сложность по времени и памяти

O(n^2)

n примерно до 5000 нормально при O(n в квадрате). На почти отсортированных данных вставки дают O(n).