Где применяется
1. Задача
У тебя короткий список чисел в случайном порядке, а нужен он от меньшего к большему. В сортировке выбором ты мог поменять местами любые две ячейки, даже далёкие друг от друга.
Здесь правило жёстче. Сравнивать можно только два числа, которые стоят рядом. Единственное разрешённое действие: поменять эту пару местами. Перескакивать через ячейки нельзя. Хватит ли только этого, чтобы отсортировать весь список?
Пусть в таблице лидеров лежит [5, 1, 4, 2, 8], а нужно получить [1, 2, 4, 5, 8]. За раз ты смотришь на одну пару соседей и меняешь её местами, если она стоит в обратном порядке.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- 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
Задачи, где сравниваются только соседи, например проверка, что список упорядочен, или сортировка короткого списка обменом соседних элементов. Проход без единой неправильной пары доказывает, что список отсортирован.
Один проход по парам соседей и проверка, что ни одна пара не растёт или ни одна не убывает.
Посчитай пары соседей в неправильном порядке, включая последний и первый элемент, и допусти не больше одной.
Строк не больше 250, поэтому сортируй целые строки пузырьком по k-й оценке от большей к меньшей.