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

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

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

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

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

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

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

Все три работают на месте с 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 insertionSort(arr: number[]): number[] {
    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;
}

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

function insertionSort(array $arr): array {
    for ($i = 1; $i < count($arr); $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

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

    public static int[] InsertionSort(int[] arr) {
        for (int i = 1; i < arr.Length; i++) {
            int key = arr[i];
            int 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) дополнительной памяти». Решение на нём обычно укладывается в O(n^2).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Элементарные сортировки (выбором, пузырьком, вставками)» чаще всего путают с этими паттернами: Быстрая сортировка (merge / quick), Сортировка без сравнений (подсчётом / поразрядная), Сортировка с пользовательским компаратором и Бинарная куча / очередь с приоритетом.

• Быстрая сортировка (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(n2).

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