Алгоритмы с нуля
Простые сортировки
Ты хочешь отсортировать массив. Быстрые алгоритмы (сортировка слиянием, быстрая сортировка) сложные: раздели массив, объедини или разбей, рекурсия. Прежде чем их учить, поймёшь простые: сортировка выбором, вставкой и пузырьком. Все работают за O(n²) — вложенный цикл в цикле. Медленные на больших данных, но быстро кодируются и просто понимаются. И вставка имеет тайну: когда массив почти отсортирован, она работает за O(n). Выучи эти, и быстрые станут понятны.
После этого урока ты разбираешься в трёх простых алгоритмах сортировки (выбором, вставкой, пузырьком), почему все O(n²) (вложенные проходы), как вставка адаптируется к O(n) на почти отсортированных данных, почему все на месте и O(1) памяти, и когда их безопасно применить (маленькие массивы или предсортированные данные) против O(n log n).
Суть: вложенные циклы = O(n²)
Все простые сортировки используют вложенную структуру: внешний цикл проходов и внутренний для поиска/постановки одного элемента. n проходов × n сравнений за проход = O(n²).
Сортировка выбором: повторно ищи минимум
Сортировка выбором делит массив на две части: отсортированный префикс (слева) и неотсортированный суффикс (справа). На каждом проходе ищешь минимум в суффиксе и переносишь его в конец префикса.
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}Почему O(n²)? На проходе i ты сканируешь n - i элементов ища минимум. Всего: n + (n-1) + (n-2) + … + 1 = n(n+1)/2 = O(n²), без разницы на порядок входа.
Сортировка вставкой: растёшь отсортированный префикс
Сортировка вставкой строит отсортированный массив слева направо, по одному элементу. Для каждого нового элемента сканируешь префикс справа налево, сдвигаешь большие элементы вправо и вставляешь новый в правильное место.
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;
}
}Почему O(n²) в худшем случае? Когда массив развёрнут (худший случай), каждая вставка требует сдвига всех предыдущих элементов. Но вот магия: вставка адаптивна. Если массив уже отсортирован или почти отсортирован, цикл while не запускается (или один раз), так что алгоритм за O(n).
Сортировка пузырьком: повторно меняешь соседей
Сортировка пузырьком повторно ходит по массиву и меняет соседние элементы если они не в порядке. Большие элементы “всплывают” в конец. После каждого прохода самый правый неотсортированный на месте.
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
}Тоже O(n²) в худшем. Проход за проходом, каждый сравнивает соседей. Пузырьёк медленнее всех трёх на практике — больше сравнений и обменов чем вставка.
Почему все O(n²) и на месте
Все три O(1) памяти — только переменные-индексы, временная для обмена. Все O(n²) в худшем из-за вложенного цикла. Но вставка особая: адаптивна.
Кодим и трассируем сортировку выбором и вставкой с полной подробностью.
Сортировка выбором:
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
// Найди минимум в arr[i..конец]
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Обменяй arr[i] и arr[minIndex]
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}Сортировка вставкой:
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i]; // Элемент для вставки
let j = i - 1;
// Сдвинь элементы больше чем key один вправо
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Вставь key в правильное место
arr[j + 1] = key;
}
}Запустим обе на неотсортированном и отсортированном вводе:
Трассируем сортировку вставкой на [5, 3, 2, 1, 4] шаг за шагом:
1
function insertionSort(arr) {
2
for (let i = 1; i < arr.length; i++) {
3
const key = arr[i];
4
let j = i - 1;
5
while (j >= 0 && arr[j] > key) {
6
arr[j + 1] = arr[j];
7
j--;
8
}
9
arr[j + 1] = key;
10
}
11
}
| Алгоритм | Худший | Лучший | Адаптивна? | Память |
|---|---|---|---|---|
| Выбор | O(n²) | O(n²) | Нет | O(1) |
| Вставка | O(n²) | O(n) | Да | O(1) |
| Пузырьёк | O(n²) | O(n) | Да (с оптимизацией) | O(1) |
Выбор в деталях:
- Всегда O(n²) потому что ищешь минимум неотсортированного суффикса, даже если массив уже отсортирован.
- Количество обменов: O(n).
Вставка в деталях:
- Худший O(n²): массив развёрнут. Каждая вставка сдвигает все предыдущие.
- Лучший O(n): массив уже отсортирован. Условие цикла while сразу ложно, только n сравнений.
- Адаптивна: количество сравнений зависит от инверсий (неупорядоченных пар). Почти отсортированный вход = мало инверсий = O(n).
Пузырьёк в деталях:
- O(n²) худший: повторные обмены соседей.
- O(n) лучший (с оптимизацией): если обменов нет за проход, отсортировано. Выйди раньше.
- Менее эффективен чем вставка на практике — больше обменов и сравнений.
Почему в сортировке выбором O(n²) даже когда массив уже отсортирован?
Вставка за O(n) на почти отсортированном массиве. Почему?
Сколько проходов делает сортировка выбором на массиве из 5 элементов?
Какой алгоритм лучше для большого уже отсортированного массива?
Что значит 'на месте' для алгоритмов сортировки?
lesson.inset.advantage
Когда использовать простые сортировки. Выбор, вставка, пузырьёк O(n²). Когда их применять? Маленькие массивы (n ≤ ~50) или почти отсортированный вход. Вставка особо: простая, на месте, сильно адаптивна. Множество реальных систем используют вставку на маленьких данных внутри оптимизированных O(n log n) алгоритмов (гибридная сортировка).
Частая ошибка
Думаешь выбор может выйти рано. Выбор всегда сканирует весь неотсортированный суффикс, даже если уже отсортирован. Не может “заметить” что отсортировано и выйти рано. Пузырьёк может (с оптимизацией: отслеживай был ли обмен), но выбор нет. Вот почему вставка лучше для предсортированных данных.
Надо отсортировать список 10 элементов. Все три простые (выбор, вставка, пузырьёк) O(n²). Какую выбрать?
Сортировка выбором: Повторно ищи минимум неотсортированной части и переноси в конец. O(n²) всегда. Никакой адаптивности.
Сортировка вставкой: Растёшь отсортированный префикс вставляя каждый новый элемент в правильное место. O(n²) худший, но O(n) на отсортированном или почти отсортированном вводе. Адаптивна.
Сортировка пузырьком: Повторно обменяй неупорядоченные соседи. O(n²) худший, O(n) лучший (с оптимизацией). Медленнее чем вставка на практике.
Все три на месте и O(1) вспомогательной памяти. Это важно на очень больших данных или в системах с ограничениями памяти.
Ключевое: Все простые O(n²) из-за вложенного цикла. Вставка особая: адаптируется к порядку входа, за O(n) на почти отсортированных данных. На больших неотсортированных, переходи на O(n log n) (сортировка слиянием, быстрая сортировка) что в следующих уроках.
Почему учить? Понимание простых учит вложенной структуре. Подготовляет к divide-and-conquer сортировке (слияние) и партиционированию (быстрая).