Просто УрокСортировка пузырьком и вставками
Разберём «Сортировка пузырьком и вставками» по шагам: короткая теория, наглядный пример, разбор типового задания и ловушки, на которых теряют баллы. В конце — что запомнить и где закрепить на практике.
Что такое сортировка пузырьком и вставками
Если в задаче нужно упорядочить числа, слова или результаты участников, важно не просто получить ответ, а понимать, почему алгоритм работает. Сортировка пузырьком и сортировка вставками помогают увидеть эту логику буквально по шагам: элементы сравниваются, меняются местами и постепенно занимают правильные позиции. Разобрав эти методы, ты научишься читать алгоритмы, находить ошибки в циклах и оценивать, сколько действий потребуется программе.
Сортировка пузырьком проходит по массиву и сравнивает соседние элементы. Если левый элемент больше правого, они меняются местами. После одного полного прохода самый большой элемент «всплывает» в конец массива. Затем алгоритм повторяет проход для оставшейся неотсортированной части.
Сортировка вставками работает иначе. Она считает левую часть массива уже отсортированной и по одному вставляет в неё следующие элементы на подходящее место. Это похоже на то, как ты раскладываешь карты в руке: новую карту двигаешь влево, пока порядок не восстановится.
Оба алгоритма просты для понимания и часто встречаются в учебных задачах, хотя для больших массивов обычно выбирают более быстрые методы.
Сортировка пузырьком по шагам
Рассмотрим массив 5, 2, 4, 1. Начинаем с первого соседнего сравнения: 5 больше 2, значит, меняем их местами. Получаем 2, 5, 4, 1. Далее сравниваем 5 и 4, затем 5 и 1. Самое большое число перемещается в конец.
После первого прохода последний элемент уже находится правильно. Поэтому на следующем проходе достаточно проверять элементы до предпоследней позиции. Так длина проверяемой части каждый раз уменьшается на один.
5, 2, 4, 1 → 2, 5, 4, 1 → 2, 4, 5, 1 → 2, 4, 1, 5
2, 4, 1, 5 → 2, 4, 1, 5 → 2, 1, 4, 5
2, 1, 4, 5 → 1, 2, 4, 5
Если за целый проход не произошло ни одной замены, массив уже отсортирован, и алгоритм можно остановить досрочно. Это улучшение не меняет худшую оценку, но экономит действия на почти упорядоченных данных.
В обычной реализации сортировка пузырьком требует порядка n² сравнений в худшем случае, где n — количество элементов. Дополнительная память обычно постоянна: O(1).
При разборе не пытайся сразу запомнить код. Сначала выпиши один проход на бумаге и отметь, какой элемент гарантированно встал на место. После этого циклы становятся намного понятнее. Закрепить идею можно в личном кабинете с бесплатной практикой.
Сортировка вставками
В сортировке вставками первый элемент условно считается отсортированным. Затем берём второй элемент и сравниваем его с элементами слева. Пока слева стоят большие значения, сдвигаем их на одну позицию вправо. Освободившееся место занимает выбранный элемент.
Пусть дан массив 5, 2, 4, 1. Сначала отсортированная часть состоит из 5. Число 2 меньше 5, поэтому оно встаёт перед ним: 2, 5. Затем берём 4: сдвигаем 5 вправо и вставляем 4 между 2 и 5. Получаем 2, 4, 5. Наконец, число 1 проходит в начало.
5 | 2, 4, 1 → 2, 5 | 4, 1
2, 5 | 4, 1 → 2, 4, 5 | 1
2, 4, 5 | 1 → 1, 2, 4, 5
В отличие от пузырьковой сортировки, здесь обычно не выполняется множество обменов. Элементы сдвигаются, а выбранное значение сохраняется во временной переменной. На почти отсортированном массиве вставки особенно удобны: приходится просматривать короткий участок.
В худшем случае сложность также равна O(n²), а в лучшем, когда массив уже упорядочен, — O(n). Память: O(1). Алгоритм устойчив: одинаковые элементы сохраняют относительный порядок.
Сравнение алгоритмов и выбор метода
Оба метода подходят для небольших массивов и учебных задач. Они работают на месте, то есть не требуют отдельного массива такого же размера. Однако внутренний принцип у них разный: пузырьковая сортировка постепенно отправляет большие элементы вправо, а сортировка вставками расширяет отсортированную левую часть.
| Признак | Пузырьком | Вставками |
|---|---|---|
| Основное действие | Обмен соседних элементов | Сдвиг и вставка |
| Лучший случай | O(n) с проверкой замен | O(n) |
| Худший случай | O(n²) | O(n²) |
| Удобна для | Понимания обменов | Почти отсортированных данных |
Если в условии спрашивают, сколько раз выполняется внешний цикл, смотри на размер неотсортированной части. Для пузырьковой сортировки она уменьшается после каждого прохода. Для вставок на каждом шаге увеличивается отсортированный префикс.
На экзамене важно не смешать количество сравнений и количество обменов. Сравнение может выполниться, даже если перестановка не нужна. При вставках вместо обмена часто считают сдвиги.
Потренироваться различать эти действия удобно через бесплатные задания в личном кабинете: после каждого шага объясняй себе, какая часть массива уже гарантированно упорядочена.
Не называй сортировку вставками обменной только потому, что элементы меняют положение. В типичном алгоритме выбранное значение временно хранится, большие элементы сдвигаются вправо, а затем выполняется одна вставка.
Типичные ошибки в задачах
Первая ошибка — неверное направление сравнения. Для сортировки по возрастанию нужно перемещать вправо большие элементы, а условие обычно имеет вид «левый элемент больше правого». Если поставить знак наоборот, получится порядок по убыванию.
Вторая ошибка — выход за границы массива. При сравнении соседей нужно остановиться до последнего допустимого индекса. В пузырьковой сортировке граница дополнительно уменьшается после каждого прохода.
Третья ошибка — потеря вставляемого элемента. Перед сдвигами его нужно сохранить во временной переменной. Иначе первое присваивание может стереть исходное значение.
Четвёртая ошибка — лишний проход. Внешний цикл может завершаться, когда отсортированная часть уже охватывает весь массив. Если используется флаг изменения, его надо сбрасывать перед каждым новым проходом.
Проверяй алгоритм на трёх наборах: уже отсортированном, отсортированном в обратном порядке и массиве с одинаковыми значениями. Такие тесты быстро показывают, правильно ли работают условие, границы и ранняя остановка.
Если готовишься к ОГЭ, полезно отдельно повторить задачи по алгоритмам. Для ЕГЭ пригодится привычка внимательно отслеживать индексы и число итераций: это часто важнее, чем механическое знание названия метода.
Что запомнить
Сортировка пузырьком сравнивает соседние элементы и после прохода отправляет максимум в конец неотсортированной части. Сортировка вставками берёт очередной элемент и вставляет его в правильное место среди уже упорядоченных слева.
Для обеих сортировок худшая сложность — O(n²), дополнительная память — O(1). Вставки обычно эффективнее на почти отсортированных данных, а пузырьковая сортировка удобна для демонстрации последовательных обменов. В любой задаче сначала определи направление сортировки, затем границы циклов и смысл каждого шага.
Следующий шаг простой: зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. После каждого ответа записывай не только результат, но и состояние массива после одного прохода. Так теория превращается в уверенный навык.
Как закрепить тему после разбора?
Возьми несколько коротких массивов и вручную выполни по одному проходу каждого алгоритма. Затем напиши псевдокод, укажи инвариант: какая часть уже отсортирована, и проверь решение на обратном порядке и повторяющихся значениях.
Какая сортировка быстрее?
В общем случае обе имеют квадратичную сложность. На почти отсортированных данных сортировка вставками часто делает меньше действий. Для больших массивов обычно используют другие алгоритмы, например сортировку слиянием или быструю сортировку.
Почему в пузырьковой сортировке уменьшается граница прохода?
После каждого полного прохода наибольший элемент текущей части оказывается в самом конце. Он уже стоит правильно, поэтому повторно сравнивать его с соседями не нужно.
Что означает O(n²)?
Это оценка роста числа действий в зависимости от размера массива. При увеличении n примерно в несколько раз количество операций в худшем случае растёт пропорционально квадрату этого числа.
Закрепить тему на практике
Теория без практики забывается за неделю. В личном кабинете Просто Урок — задания именно по этой теме с проверкой каждого шага. Регистрация бесплатная.