Алгоритмы сортировки с примерами кода на Python

Что такое алгоритмы сортировки и как их сравнивают

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

Сравнивают алгоритмы по четырем признакам:

• Время работы в нотации O-большое: как растет число операций при росте размера массива n. O(n log n) для миллиона элементов - это около 20 миллионов операций, O(n^2) - около триллиона.
• Дополнительная память: сортирует ли алгоритм на месте или создает копии.
• Устойчивость (стабильность): сохраняется ли исходный порядок равных элементов. Это важно при сортировке по нескольким полям.
• Адаптивность: работает ли алгоритм быстрее на почти отсортированных данных.

Код ниже использует только циклы, списки и рекурсию. Если эти темы пока даются тяжело, сначала пройдите базу по плану из статьи с чего начать изучение Python, а для экспериментов удобно настроить VS Code с отладчиком: так видно, как элементы меняются местами на каждом шаге.

Сравнение алгоритмов сортировки: таблица сложности

Здесь k - диапазон значений для сортировки подсчетом. Пузырек O(n) в лучшем случае получает только с проверкой "были ли обмены", как в примере ниже.

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

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

def bubble_sort(arr):
    a = arr[:]
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

print(bubble_sort([5, 1, 4, 2, 8]))  # [1, 2, 4, 5, 8]

Флаг swapped останавливает работу, если за проход не было ни одного обмена: массив уже отсортирован. Внутренний цикл каждый раз короче на i, потому что хвост уже на своих местах.

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

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

Вставками

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

def insertion_sort(arr):
    a = arr[:]
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

Выбором

На каждом шаге ищем минимум в неотсортированной части и ставим его в начало. Всегда делает O(n^2) сравнений, зато не больше n обменов. Неустойчива: равные элементы могут поменяться местами.

def selection_sort(arr):
    a = arr[:]
    for i in range(len(a)):
        m = min(range(i, len(a)), key=a.__getitem__)
        a[i], a[m] = a[m], a[i]
    return a

Сортировка слиянием (merge sort)

Классический пример подхода "разделяй и властвуй":

1. Делим массив пополам.
2. Рекурсивно сортируем каждую половину.
3. Сливаем две отсортированные половины в одну, сравнивая их первые элементы.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Всегда O(n log n), даже на худших данных, и устойчива: благодаря условию <= из двух равных элементов первым попадает левый. Минус - нужна дополнительная память O(n). Слияние хорошо подходит для связанных списков и внешней сортировки, когда данные не помещаются в оперативную память и лежат в файлах.

Быстрая сортировка (quicksort)

Выбираем опорный элемент (pivot), раскладываем остальные на меньшие и большие и рекурсивно сортируем обе части. Короткая версия на списковых включениях читается почти как описание алгоритма:

import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

Случайный pivot защищает от худшего случая O(n^2), который возникает, если всегда брать первый элемент уже отсортированного массива. Отдельный список equal спасает при большом числе одинаковых значений.

У этой версии есть минус: она создает новые списки и тратит память. На собеседовании могут попросить сортировку на месте. Вот вариант со схемой разбиения Хоара:

def quick_sort_inplace(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    pivot = a[(lo + hi) // 2]
    i, j = lo, hi
    while i <= j:
        while a[i] < pivot:
            i += 1
        while a[j] > pivot:
            j -= 1
        if i <= j:
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1
    quick_sort_inplace(a, lo, j)
    quick_sort_inplace(a, i, hi)

В среднем quicksort очень быстрая на практике, поэтому ее вариации используются во многих стандартных библиотеках, например introsort в C++.

Пирамидальная сортировка и сортировка подсчетом

Пирамидальная (heapsort) строит из массива двоичную кучу и по одному извлекает минимум. Гарантирует O(n log n) без дополнительной памяти. В Python куча есть в модуле heapq, и короткий вариант выглядит так: heapq.heapify(a), затем [heapq.heappop(a) for _ in range(len(a))].

Подсчетом (counting sort) не сравнивает элементы, а считает, сколько раз встречается каждое значение. Работает за O(n + k), но только для целых чисел из небольшого диапазона: оценок от 1 до 5, возрастов, байтов.

def counting_sort(arr, max_value):
    counts = [0] * (max_value + 1)
    for x in arr:
        counts[x] += 1
    result = []
    for value, c in enumerate(counts):
        result.extend([value] * c)
    return result

print(counting_sort([3, 0, 2, 3, 1], 3))  # [0, 1, 2, 3, 3]

Встроенная сортировка в Python: sorted() и list.sort()

В реальном коде на Python свои алгоритмы сортировки не пишут. Встроенная сортировка написана на C, устойчива и адаптивна. Исторически это Timsort, гибрид слияния и вставок, придуманный Тимом Петерсом в 2002 году. Начиная с Python 3.11 в CPython изменили стратегию слияния отсортированных кусков на Powersort: результат тот же, гарантии те же, порядок слияний оптимальнее.

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

users = [("Анна", 31), ("Борис", 25), ("Вера", 31)]
print(sorted(users, key=lambda u: u[1]))
# [('Борис', 25), ('Анна', 31), ('Вера', 31)]: Анна осталась перед Верой

words = ["banana", "Apple", "cherry"]
print(sorted(words, key=str.lower))  # ['Apple', 'banana', 'cherry']

Разница простая: sorted() принимает любой итерируемый объект и возвращает новый список, list.sort() меняет список на месте и возвращает None. Частая ошибка новичков - написать nums = nums.sort() и получить None.

Для сортировки по нескольким полям используйте кортеж в key. Числа можно развернуть минусом, а для строк в обратном порядке удобнее сортировать дважды, пользуясь устойчивостью.

from operator import itemgetter

rows = [("Вера", 31), ("Анна", 31), ("Борис", 25)]
# по возрасту по убыванию, при равенстве по имени
print(sorted(rows, key=lambda r: (-r[1], r[0])))
# [('Анна', 31), ('Вера', 31), ('Борис', 25)]
print(sorted(rows, key=itemgetter(1)))

Больше задач на эту тему собрано по тегам алгоритмы и Python.

Что знать для собеседования и как сравнить скорость

На собеседовании junior чаще всего просят:

1. Написать пузырек или вставками и назвать их сложность.
2. Объяснить идею быстрой сортировки и слияния, их сложность и худший случай quicksort.
3. Рассказать, что такое устойчивая сортировка и зачем она нужна.
4. Сказать, какую сортировку использует Python и почему sorted быстрее самописной.

Убедиться в разнице скоростей проще всего самому. Поместите функции из статьи в один файл и добавьте замер:

import random, timeit

data = [random.randint(0, 10_000) for _ in range(2000)]

for fn in (bubble_sort, insertion_sort, merge_sort, quick_sort, sorted):
    t = timeit.timeit(lambda: fn(data), number=3)
    print(f"{fn.__name__:15} {t:.3f} c")

Типовые вопросы по Python для собеседования собраны в отдельной статье о собеседовании Python junior.