Алгоритмы сортировки: пузырёк, выбор и вставки на Python

Что такое алгоритм сортировки

Алгоритм сортировки — это точная последовательность сравнений и перестановок, после которой элементы стоят по возрастанию или по убыванию. Компьютер не «видит» весь список сразу: он умеет сравнить два элемента и поменять их местами.

Сортировку мы делаем постоянно: расставляем книги по росту, раскладываем карты в руке, строимся на физкультуре. Человек делает это интуитивно, а программе нужен рецепт. Разные рецепты дают один и тот же результат, но тратят разное число действий. Поэтому алгоритмы сортировки — классический материал для разговора о том, что один способ бывает быстрее другого. Программу без такого рецепта написать не получится: компьютер не догадается сам, что значит «по порядку».

По федеральной образовательной программе одномерные массивы изучают в 9 классе информатики^[1], и упорядочивание массива — естественная задача этой темы. Учебники, написанные по ФОП, обычно показывают на нём вложенные циклы. На Python массив — это список, поэтому перед чтением полезно вспомнить, как устроены списки в Python и их индексы.

Сортировка пузырьком: соседи меняются местами

Сортировка пузырьком — это способ, при котором программа идёт по списку слева направо, сравнивает соседние элементы и меняет их местами, если левый больше правого. После первого прохода самый большой элемент оказывается в конце.

Название понятное: крупные числа «всплывают» к концу списка, как пузыри в воде. После каждого прохода ещё один элемент встаёт на своё место, поэтому следующий проход можно делать на одну пару короче. Посмотрим на список [5, 2, 9, 1, 7].

Проход	Список после прохода	Сравнений	Обменов
1	[2, 5, 1, 7, 9]	4	3
2	[2, 1, 5, 7, 9]	3	1
3	[1, 2, 5, 7, 9]	2	1
4	[1, 2, 5, 7, 9]	1	0

a = [5, 2, 9, 1, 7]
n = len(a)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
print(a)

Внешний цикл считает проходы, внутренний — пары соседей. Запись a[j], a[j + 1] = a[j + 1], a[j] меняет два элемента местами в одну строку, без лишней переменной. Руководство PEP 8 советует давать переменным понятные имена, но для индексов циклов короткие i и j — общепринятая традиция. Обратите внимание на 4-й проход: в нём не было ни одного обмена, значит, список уже упорядочен. Улучшенный пузырёк заводит флажок «был ли обмен» и останавливается досрочно, если обменов не было.

Сортировка выбором: найди минимум и поставь вперёд

Сортировка выбором — это способ, при котором на каждом шаге программа ищет минимальный элемент среди ещё не упорядоченных и ставит его на первое свободное место.

Так раскладывают карточки с числами на столе: нашли самую маленькую — положили слева, потом из оставшихся снова ищем самую маленькую. Для списка [5, 2, 9, 1, 7] первым шагом находим 1 и меняем её с 5, получаем [1, 2, 9, 5, 7]. Двойка уже на месте, обмен не нужен. Дальше минимум из [9, 5, 7] — пятёрка, меняем с девяткой. Последний шаг ставит 7 перед 9.

a = [5, 2, 9, 1, 7]
n = len(a)
for i in range(n - 1):
    m = i
    for j in range(i + 1, n):
        if a[j] < a[m]:
            m = j
    a[i], a[m] = a[m], a[i]
print(a)

Переменная m хранит индекс текущего минимума. У этого способа приятная черта: обменов мало, не больше чем элементов минус один. Зато сравнений всегда одинаково много, даже если на вход дали уже упорядоченный список.

Сортировка вставками: как карты в руке

Сортировка вставками — это способ, при котором программа берёт очередной элемент и сдвигает его влево, пока слева не окажется число меньше или равное. Левая часть списка всё время остаётся упорядоченной.

Так держат карты: каждую новую вставляют на нужное место среди уже разложенных. В коде элемент запоминают в переменной x, а большие соседи по одному сдвигаются вправо, освобождая место.

a = [5, 2, 9, 1, 7]
for i in range(1, len(a)):
    x = a[i]
    j = i - 1
    while j >= 0 and a[j] > x:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = x
print(a)

Здесь работает цикл while, потому что заранее неизвестно, на сколько позиций сдвинется элемент. Если список почти упорядочен, сдвигов почти нет, и вставки заканчиваются очень быстро. Выбирать этот алгоритм сортировки стоит, когда данные приходят по одному и их нужно сразу ставить на место. Порядок условий в while j >= 0 and a[j] > x важен: сначала проверяем, что индекс не вышел за начало списка, и только потом смотрим на элемент.

Сколько сравнений делает каждый алгоритм сортировки

Для списка из n элементов пузырёк без досрочной остановки и сортировка выбором делают n(n − 1)/2 сравнений: для 5 элементов это 10, для 100 — уже 4950. Вставки на упорядоченном списке обходятся n − 1 сравнением.

Мы посчитали действия программой со счётчиками на трёх списках по 5 элементов. Обменом для вставок считается каждый сдвиг элемента вправо.

Входной список	Пузырьком: сравнения / обмены	Выбором: сравнения / обмены	Вставками: сравнения / сдвиги
[5, 2, 9, 1, 7]	10 / 5	10 / 3	7 / 5
[1, 2, 3, 4, 5] — уже по порядку	10 / 0	10 / 0	4 / 0
[5, 4, 3, 2, 1] — наоборот	10 / 10	10 / 2	10 / 10

Если список вырастет в 10 раз, число сравнений у этих трёх способов вырастет примерно в 100 раз: оно зависит от квадрата длины. Для 10 чисел разницы не заметно, а для миллиона простые способы становятся слишком медленными. Поэтому в настоящих программах используют более хитрые алгоритмы, а эти три — учебные: на них удобно понять идею и посчитать шаги вручную.

Встроенные sorted() и list.sort() в Python

В Python есть 2 готовых инструмента: функция sorted() возвращает новый упорядоченный список, а метод list.sort() упорядочивает сам список и возвращает None.

ocenki = [4, 5, 3, 5, 4]
print(sorted(ocenki))
print(sorted(ocenki, reverse=True))
slova = ["кот", "бегемот", "ёж", "слон"]
slova.sort(key=len)
print(slova)

[3, 4, 4, 5, 5]
[5, 5, 4, 4, 3]
['ёж', 'кот', 'слон', 'бегемот']

Параметр reverse=True переворачивает порядок, а key задаёт, по какому признаку сравнивать: здесь по длине слова. Встроенная сортировка устойчива: элементы с одинаковым ключом сохраняют исходный порядок, — так сказано в официальной документации Python^[2]. Строки сравниваются по кодам символов, поэтому заглавные буквы встают раньше строчных, а «ё» оказывается после «я». Больше полезных функций собрано в статье о встроенных функциях Python.

Тренажёр: сортировка на столбиках

Тренажёр в начале страницы показывает числа столбиками разной высоты: выберите способ — пузырьком, выбором или вставками — и следите, как столбики меняются местами.

Кнопка «Новый массив» перемешивает столбики, «Шаг» выполняет одно действие, а «▶ Запустить» проигрывает всю сортировку. Счётчики сравнений и перестановок обновляются на ходу. Попробуйте одно упражнение: запустите все три способа на одном массиве и запишите числа в тетрадь. Потом нажмите «Шаг» несколько раз для пузырька и предскажите вслух, какие два столбика сравнятся следующими. В исследовании Roediger и Karpicke самопроверка закрепляла материал лучше, чем повторное чтение текста^[3], и предсказание с проверкой работает по тому же принципу. Результаты тренажёров сохраняются только в вашем браузере.

«Пузырёк — самый медленный, его нельзя использовать никогда». Это миф: на почти упорядоченных данных пузырёк с флажком заканчивает работу за один проход, а на списке из 10 чисел разница между способами не превышает долей секунды.

«Встроенный sorted() — это просто пузырёк, только спрятанный». Такое утверждение не подтверждается официальной документацией Python: в CPython используется другой, гораздо более быстрый алгоритм, и он оптимизирован под частично упорядоченные данные.

Где алгоритмы сортировки встречаются в школе и на экзаменах

Упорядочивание — это часть темы «одномерные массивы» в 9 классе по ФОП, а в ЕГЭ задачи на обработку данных часто проще решить, если сначала расставить числа по порядку.

По материалам ФИПИ, в ЕГЭ по информатике есть задания на написание программ, например 17, 24, 25 и 26^[4]. В школьном курсе такие упражнения нужны, чтобы научиться писать вложенные циклы с индексами и не путаться в границах. На экзамене чаще пользуются готовой функцией: например, чтобы найти несколько наибольших значений, достаточно упорядочить список и взять срез с конца. Как Python помогает в экзаменационных задачах, разобрано на странице про ЕГЭ по информатике и Python. А потренировать индексы можно на подборке задач на списки с автопроверкой.

Когда самописная сортировка не нужна

Писать её вручную не нужно, если задача не проверяет именно умение её написать: в рабочих программах берут встроенную функцию. Вот 4 случая, когда учебные способы только мешают.

Данных больше 10 000. Квадратичное число сравнений сделает программу заметно медленной.
Нужно найти 1 максимум или минимум. Хватит функций max() и min() — упорядочивать весь список незачем.
Экзамен с ограничением по времени. Готовый sorted() пишется за 1 строку и не содержит ошибок в индексах.
В списке смешаны числа и строки. Python 3 не умеет сравнивать 5 и «пять» и выдаст ошибку TypeError.

Чего делать нельзя

Нельзя путать sorted() и sort(): первая возвращает новый список, а метод меняет старый и возвращает None. Остальные частые промахи собраны ниже.

Нельзя писать a = a.sort() — в переменной окажется None, а список пропадёт.
Не следует выходить внутренним циклом за границу: индекс j + 1 должен быть меньше длины, иначе будет IndexError.
Не стоит менять элементы через одну переменную вроде a[j] = a[j + 1]; a[j + 1] = a[j] — одно значение потеряется.
Не стоит сравнивать числа, введённые как строки: «10» окажется меньше «9», ведь сравнение идёт по символам.
Нельзя оценивать скорость на 5 элементах — разница между способами видна только на больших списках, не раньше нескольких тысяч чисел.

Не стоит паниковать, если ошибка всё-таки появилась: сообщение Python подскажет её тип и строку. Например, смешанный список разобран на странице про ошибку TypeError.

Источники

[1] Приказ Минпросвещения России от 18.05.2023 № 370 «Об утверждении федеральной образовательной программы основного общего образования».

[2] The Python Tutorial (официальная документация Python 3). Python Software Foundation.

[3] Roediger H. L., Karpicke J. D. Test-enhanced learning: Taking memory tests improves long-term retention // Psychological Science. 2006. Vol. 17, № 3. P. 249–255.

[4] ФИПИ. Методические рекомендации для обучающихся по организации индивидуальной подготовки к ЕГЭ 2026 года. Информатика. М., 2026.

Вопросы и ответы

Какой способ самый быстрый из трёх?

Зависит от данных. На почти упорядоченном списке быстрее всех вставки, на перевёрнутом все три делают одинаково много сравнений, а выбор выигрывает по числу обменов.

Как упорядочить по убыванию?

В самописном коде поменяйте знак сравнения на противоположный. Со встроенной функцией добавьте параметр reverse=True.

Можно ли упорядочить строку?

Функция sorted('кот') вернёт список букв ['к', 'о', 'т']. Строкой результат сам не станет: соедините буквы через ''.join().

Что значит «устойчивая» сортировка?

Равные по ключу элементы не меняют взаимного порядка. Если упорядочить учеников по оценке, те, у кого одинаковая оценка, останутся в исходном порядке, например по алфавиту.

Зачем учить пузырёк, если есть sorted()?

Чтобы научиться писать вложенные циклы, работать с индексами и считать шаги программы. Эти навыки пригодятся в любой задаче, а не только когда нужно упорядочить данные. Готовая функция их не заменяет.

Почему 'Яблоко' стоит раньше 'арбуз'?

Python сравнивает коды символов, а у заглавных букв коды меньше, чем у строчных. Без параметра key регистр не получится игнорировать, поэтому передайте key=str.lower.