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

Алгоритм сортировки расставляет элементы списка в заданном порядке, например по возрастанию. Простые методы, такие как пузырёк, выбор и вставки, делают число сравнений, растущее как квадрат размера списка. Быстрая сортировка в среднем справляется заметно меньшим числом сравнений. Статья для тех, кто умеет писать циклы и функции на Python. Вы разберёте четыре алгоритма, запустите их со счётчиком сравнений и увидите, как растёт разница с размером списка.

Описания алгоритмов сверены с Википедией и учебником Седжвика и Уэйна, поведение встроенной сортировки — с документацией Python. Код проверен запуском на Python 3.13. Данные на октябрь 2026 года.

Зачем сортировать и что такое устойчивость

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

Устойчивость заметна, когда в списке есть записи с равными ключами. Например, люди с одинаковым годом рождения: устойчивая сортировка по году оставит их в прежнем порядке.

Сортировка пузырьком

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

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

def пузырёк(данные):
    a = list(данные)
    for проход in range(len(a) - 1):
        обмен = False
        for i in range(len(a) - 1 - проход):
            if меньше(a[i + 1], a[i]):
                a[i], a[i + 1] = a[i + 1], a[i]
                обмен = True
        if not обмен:          # обменов не было — список уже упорядочен
            break
    return a

Функцию меньше мы определим в полном примере ниже: она сравнивает два элемента и считает сравнения.

Сортировка выбором

Идея: находим наименьший элемент среди ещё не упорядоченных и ставим его на первое место, затем ищем наименьший среди оставшихся и ставим на второе. Википедия отмечает, что в худшем, среднем и лучшем случаях выбор делает порядка n² операций. Даже на уже отсортированном списке он делает те же сравнения.

def выбор(данные):
    a = list(данные)
    for i in range(len(a) - 1):
        мин = i
        for j in range(i + 1, len(a)):
            if меньше(a[j], a[мин]):
                мин = j
        a[i], a[мин] = a[мин], a[i]
    return a

Сортировка вставками

Идея: так раскладывают карты в руке. Берём очередной элемент и вставляем его на нужное место среди уже упорядоченных слева. По Седжвику и Уэйну, на случайных данных вставки делают в среднем около N²/4 сравнений, в худшем случае около N²/2, а в лучшем — N−1. Метод хорошо работает на данных, которые уже почти упорядочены.

def вставки(данные):
    a = list(данные)
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0 and меньше(x, a[j]):
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a

Быстрая сортировка

Идея «разделяй и властвуй»: выбираем опорный элемент, делим остальные на меньшие и большие, затем рекурсивно сортируем обе части. Седжвик и Уэйн пишут, что это самый широко используемый алгоритм сортировки. В среднем он делает порядка 2N·ln N сравнений, а в худшем случае порядка N²/2; случайное перемешивание перед сортировкой защищает от худшего случая.

def быстрая(данные):
    if len(данные) <= 1:
        return list(данные)
    опорный = данные[len(данные) // 2]
    меньшие, равные, большие = [], [], []
    for x in данные:
        if меньше(x, опорный):
            меньшие.append(x)
        elif меньше(опорный, x):
            большие.append(x)
        else:
            равные.append(x)
    return быстрая(меньшие) + равные + быстрая(большие)

Эта версия учебная: она создаёт новые списки, поэтому тратит память. Версии, которые работают на месте, быстрее, но сложнее.

Сортировка слиянием

Идея: делим список пополам, сортируем каждую половину, затем сливаем две упорядоченные половины в один список. По Википедии, сортировка слиянием делает порядка n·log n операций во всех случаях, а по Седжвику и Уэйну гарантирует такое время. Она устойчива. Цена за это — дополнительная память для массива. Код мы не приводим: для обзора достаточно таблицы ниже.

Сколько это стоит

Запустим четыре алгоритма на одном и том же случайном списке и посчитаем сравнения. Список составлен из случайных чисел с фиксированным зерном, поэтому вывод повторяется.

import random

сравнений = 0

def меньше(a, b):
    """Сравнивает два элемента и считает сравнения."""
    global сравнений
    сравнений += 1
    return a < b

алгоритмы = [("пузырёк", пузырёк), ("выбор", выбор), ("вставки", вставки), ("быстрая", быстрая)]

random.seed(1)
print("размер  алгоритм  сравнений")
for размер in (100, 1000):
    данные = [random.randint(0, 10_000) for _ in range(размер)]
    for имя, f in алгоритмы:
        сравнений = 0
        результат = f(данные)
        assert результат == sorted(данные)
        print(f"{размер:>6}  {имя:<8}  {сравнений:>9}")

Функции пузырёк, выбор, вставки и быстрая из разделов выше нужно поместить в тот же файл перед этим кодом. Вывод при запуске на Python 3.13:

размер  алгоритм  сравнений
   100  пузырёк        4905
   100  выбор          4950
   100  вставки        2327
   100  быстрая        1049
  1000  пузырёк      499464
  1000  выбор        499500
  1000  вставки      245727
  1000  быстрая       17356

При росте списка в 10 раз сравнений у пузырька стало больше почти в 100 раз, а у быстрой сортировки примерно в 16. Выбор делает ровно n(n−1)/2 сравнений: 4950 для 100 элементов и 499 500 для 1000. Вставки на случайных данных дали около четверти от n², что совпадает с оценкой N²/4 из учебника. Быстрая сортировка в нашей версии делает два сравнения на элемент (меньше и больше опорного), поэтому цифры у неё чуть выше теоретических.

Значения взяты из карточек алгоритмов в Википедии и из перечня устойчивых и неустойчивых сортировок на странице «Алгоритм сортировки». Оценки показывают рост при увеличении размера списка, а не время в секундах.

Встроенная сортировка Python

На практике Python используют не самописную сортировку, а встроенную. Документация описывает две возможности: функция sorted возвращает новый отсортированный список, а метод list.sort меняет список на месте. Параметр key задаёт ключ, а reverse=True — обратный порядок. Документация гарантирует, что сортировка устойчива: записи с одинаковым ключом сохраняют исходный порядок. Алгоритм — Timsort, который использует упорядоченность, уже имеющуюся в данных.

люди = [("Анна", 1990), ("Борис", 1985), ("Вера", 1990), ("Глеб", 1985)]

# Встроенная сортировка Python устойчива: у равных годов порядок имён сохраняется
print(sorted(люди, key=lambda p: p[1]))

# list.sort сортирует на месте, sorted возвращает новый список
числа = [5, 2, 9, 1]
новый = sorted(числа, reverse=True)
числа.sort()
print(новый, числа)

[('Борис', 1985), ('Глеб', 1985), ('Анна', 1990), ('Вера', 1990)]
[9, 5, 2, 1] [1, 2, 5, 9]

Внутри каждого года порядок имён сохранился: Борис перед Глебом, Анна перед Верой. Так же было в исходном списке.

Как выбрать алгоритм

Условия и ограничения

Версия

Python 3.13, октябрь 2026 — код проверен запуском; число сравнений у случайных списков зависит от зерна генератора.

Язык

Примеры на Python — в C и C++ реализация отличается, но идея алгоритмов та же.

Данные

Учебные списки — списки из 100 и 1000 чисел показывают рост, но не заменяют измерений на реальных данных.

Сложность

Рост, а не секунды — оценка O(…) описывает, как растёт число операций, а не время работы в секундах.

Устойчивость

Не у всех алгоритмов — быстрая сортировка и выбор в стандартной реализации неустойчивы.

Частые ошибки

• Берут пузырёк для больших списков: число сравнений растёт как квадрат размера.
• Путают сложность и время в секундах: O(n²) говорит о росте, а не о конкретной скорости.
• Не учитывают устойчивость, когда сортируют по нескольким признакам подряд.
• Пишут свою сортировку вместо встроенной sorted в рабочем коде.
• Берут первый элемент опорным в быстрой сортировке на уже упорядоченных данных и получают худший случай.
• Забывают, что list.sort меняет список на месте и возвращает None, а sorted возвращает новый список.

Короткий вывод

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