Где применяется
1. Задача
У тебя список чисел в случайном порядке, а нужен он от меньшего к большему. В лобби игры пять игроков со счётом 40, 15, 27, 8 и 31. Ты хочешь построить таблицу лидеров по порядку, от меньшего счёта к большему.
До сих пор ты искал в списке одно значение. Теперь нужно упорядочить весь список. Самый простой способ сортировки: раз за разом задавать один и тот же вопрос. Какое число самое маленькое среди тех, что ещё не поставлены на место?
Отвечай на этот вопрос снова и снова, и список окажется отсортирован.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитinsertionSort([5, 2, 4, 6, 1, 3])Сортируем [5, 2, 4, 6, 1, 3] вставками. Левая часть уже отсортирована; в начале это одно число 5.
Одна операция: одно сравнение или одно перемещение. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n²)O(n²)O(n log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- 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 примерно до 5000 нормально при O(n в квадрате). На почти отсортированных данных вставки дают O(n).
На LeetCode
Сортировка выбором слишком медленная для больших тестов LeetCode, поэтому здесь задачи с маленьким n, до нескольких тысяч. Нужно упорядочить короткий список или сравнить список с его отсортированной копией.
Отсортируй копию выбором и посчитай места, где она отличается от исходного списка.
На каждом проходе бери самого высокого из оставшихся и меняй местами имя вместе с ростом.
Всего 300 значений, поэтому сортировка выбором на месте проходит, хотя можно и за один проход.