Алгоритмы с нуля
Зачем сортировать?
У тебя есть несортированные данные и трудная задача: найти дубликаты, поискать значение, найти медиану или две ближайшие цифры. Каждая выглядит сложной и дорогой. Но что если сначала упорядочить данные? Отсортированный массив как отсортированный справочник — внезапно трудные задачи становятся тривиальными. Цена: один sort за O(n log n). Награда: разблокируй O(log n) поиск, мгновенное обнаружение дубликатов, нахождение медианы за линейное время и ещё.
После этого урока ты понимаешь, что значит “отсортировано”, почему сортировка работает предварительной обработкой, что разблокирует быстрые алгоритмы (бинарный поиск, поиск дубликатов, медиана, ближайшие пары), и когда сортировка стоит первоначальной цены, а когда нет.
Что значит “отсортировано”?
Массив отсортирован (или в отсортированном порядке), когда каждый элемент меньше или равен следующему. Для массива чисел [3, 1, 4, 1, 5, 9, 2, 6]:
- Отсортировано по возрастанию: [1, 1, 2, 3, 4, 5, 6, 9]
- Отсортировано по убыванию: [9, 6, 5, 4, 3, 2, 1, 1]
Порядок зафиксирован, на него можно полагаться.
Большая идея: сортировка как предварительная обработка
Сортировка — это шаг предварительной обработки: делаешь один раз, потом получаешь выгоды для всех будущих операций. Думай как организация библиотеки: потратишь время, отсортировав книги по названию (O(n log n)), и потом каждый поиск мгновенен (O(log n)). Сделай один раз, получай выгоду всегда.
Какие задачи становятся лёгкими после сортировки?
1. Бинарный поиск (поиск значения)
Несортированный массив: Чтобы узнать, есть ли значение, нужно сканировать массив линейно. Худший случай: O(n).
Отсортированный массив: Используй бинарный поиск. Режь пространство поиска пополам каждый шаг. Худший случай: O(log n).
Для массива из 1 миллиона элементов:
- Линейный поиск: ~500 000 сравнений (в среднем)
- Бинарный поиск: ~20 сравнений
Это ускорение в 25 000 раз.
2. Поиск дубликатов (есть ли повторы в массиве?)
Несортированный массив: Сравни каждый элемент со всеми остальными. Вложенные циклы. O(n²).
function hasDuplicateUnsorted(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true;
}
}
return false; // O(n²)
}Отсортированный массив: Ходи один раз. Если два соседа равны, есть дубликат. O(n).
function hasDuplicateSorted(arr) {
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] === arr[i + 1]) return true;
}
return false; // O(n)
}Цена: O(n log n) сортировка один раз. Выгода: O(n) вместо O(n²).
3. Нахождение медианы (средний элемент)
Несортированный массив: Найти n/2-й наименьший элемент. Требует сложный алгоритм (median-of-medians, или сортировка). O(n) в среднем, но трудно.
Отсортированный массив: Медиана на индексе n/2. Прямой доступ. O(1).
4. Нахождение ближайшей пары (два значения с минимальной разницей)
Несортированный массив: Сравни каждую пару со всеми другими. O(n²).
Отсортированный массив: Ходи по соседям. Ближайшая пара обязана быть соседями в отсортированном порядке. O(n).
Решение “сортировать или нет”
Сортировка всегда стоит O(n log n). Вопрос: стоит ли?
Сортируй если:
- Ты будешь делать много запросов (поиски, проверки, медиана) на одних данных. Каждый запрос быстрее, и стоимость сортировки амортизируется.
- Отсортированный порядок сам решает твою задачу (например, найти ближайшую пару, найти медиану).
- Ты в сценарии “читаю много, пишу раз”: напиши данные один раз, читай много раз.
Не сортируй если:
- Нужна одна операция (один поиск, одна проверка) на данных. O(n log n) сортировка + O(log n) поиск не лучше чем O(n) линейный поиск.
- Данные уже отсортированы (или почти). Используй insertion sort — O(n).
- Сортировка уничтожает информацию, что нужна (например, индексы). Держи несортированную версию.
Запрограммируем пример поиска дубликатов, показав огромную разницу.
O(n²) без сортировки:
function hasDuplicateNaive(arr) {
// Сравни каждый элемент со всеми другими
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) {
return true; // Нашли дубликат
}
}
}
return false; // Нет дубликатов
}O(n log n) с сортировкой:
function hasDuplicateSorted(arr) {
// Сначала, отсортируй массив
arr.sort((a, b) => a - b);
// Теперь проверь только соседей
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] === arr[i + 1]) {
return true; // Нашли дубликат
}
}
return false; // Нет дубликатов
}Давайте запустим оба на разных размерах:
Давайте трассируем поиск дубликатов рядом. Массив: [5, 2, 5, 8, 1].
Несортированный (O(n²)):
1
for (let i = 0; i < arr.length; i++) {
2
for (let j = i + 1; j < arr.length; j++) {
3
if (arr[i] === arr[j]) return true;
4
}
5
}
Нашли совпадение после 2 сравнений — повезло. Худший случай: нет дубликатов. Сравнили бы все пары: 1 + 2 + 3 + 4 = 10 сравнений для всего 5 элементов. Это O(n²).
Отсортированный (O(n log n)):
После сортировки [5, 2, 5, 8, 1] → [1, 2, 5, 5, 8]:
1
arr.sort(...);
2
for (let i = 0; i < arr.length - 1; i++) {
3
if (arr[i] === arr[i + 1]) return true;
4
}
Только 1 сравнение после сортировки (плюс O(n log n) sort). Для большого массива без дубликатов, сканировали бы отсортированный массив один раз: 4 сравнения, а не 10.
Вот сравнение сложности для поиска дубликатов:
| Подход | Полная стоимость | Когда использовать |
|---|---|---|
| Вложенный цикл (без sort) | O(n²) | Только маленькие массивы (n ≤ ~100) |
| Sort + проверка соседей | O(n log n) | Средние+ массивы, особенно если нужен порядок потом |
Для разных размеров массива:
| n | O(n²) | O(n log n) |
|---|---|---|
| 100 | 10 000 ops | ~700 ops |
| 1 000 | 1 000 000 ops | ~10 000 ops |
| 10 000 | 100 000 000 ops | ~130 000 ops |
| 100 000 | 10 000 000 000 ops | ~1 700 000 ops |
Паттерн держится для всех задач, разблокируемых сортировкой: Нахождение медианы, нахождение ближайшей пары, слияние отсортированных массивов. Один раз отсортирован, остальное линейно или логарифмично.
У тебя несортированный массив, и нужно узнать, есть ли конкретное значение. Лучше отсортировать первым или сканировать линейно?
Ты отсортировал массив за O(n log n), потом поискал его 100 раз бинарным поиском (O(log n) за раз). Какова полная стоимость?
Какова сложность поиска дубликатов в отсортированном массиве, пройдя соседей?
Когда НЕ стоит сортировать перед решением задачи?
Нужно найти медиану (средний элемент) несортированного массива. После сортировки, какова стоимость нахождения медианы?
Граничные случаи
Сортировка на месте vs копирование. Если отсортируешь исходный массив, потеряешь первоначальный порядок. Иногда нужны оба — отсортированный порядок для запросов и первоначальные индексы. В этом случае создай копию массива для сортировки, или используй массив индексов, чтобы не менять исходный. Это стоит дополнительную память, но сохраняет информацию.
Частая ошибка
Переизбыточная сортировка. Не сортируй “чтобы быть в безопасности” для одной операции. Если поищешь один раз или проверишь дубликаты один раз, линейное время дешевле сортировки. Сортируй только когда переиспользуешь отсортированный порядок много раз, или когда сама задача требует порядка (медиана, ближайшая пара и т. д.).
Нужно обнаружить дубликаты в массиве из 100 000 элементов. Используешь ли ты O(n²) вложенные циклы или O(n log n) sort + скан соседей?
Что такое сортировка? Упорядочение элементов в неубывающем (или невозрастающем) порядке.
Зачем сортировать? Сортировка — предварительная обработка: потрать O(n log n) один раз, получи выгоды потом.
Какие задачи становятся лёгкими?
- Поиск: O(n log n) sort → O(log n) бинарный поиск. Итого: O(n log n).
- Поиск дубликатов: O(n log n) sort → O(n) скан соседей. Итого: O(n log n).
- Медиана: O(n log n) sort → O(1) прямой доступ. Итого: O(n log n).
- Ближайшая пара: O(n log n) sort → O(n) скан соседей. Итого: O(n log n).
Когда сортировать:
- Будешь делать много запросов или операций на данных.
- Задача требует отсортированный порядок (медиана, ближайшая пара, слияние).
- Ты в сценарии “читаю много”: напиши один раз, читай много.
Когда НЕ сортировать:
- Делаешь одну операцию. O(n) линейный дешевле чем O(n log n) sort + O(log n) поиск.
- Данные уже отсортированы. Используй более быструю сортировку (insertion sort) или пропусти.
Основное понимание: Сортировка не магия; стоит O(n log n). Но разблокирует O(log n) поиск, O(n) поиск дубликатов, O(n) нахождение медианы. Вот трейдофф. Плати один раз, получай выгоду много раз.
Далее ты узнаешь конкретные алгоритмы сортировки — простые sorts (bubble, insertion, selection), что медленные, и быстрые sorts (merge sort, quicksort), что эффективные.