Сортировки: пузырёк, вставки, быстрая, слиянием

Пять классических сортировок с кодом, таблицей сложностей и объяснением, какую выбрать в лабораторной и что ответить про устойчивость.

В лабораторной обычно требуют реализовать две-три сортировки и сравнить их по времени на массивах разного размера. Ниже — минимальные корректные реализации и то, что нужно сказать про каждую.

Пузырьковая — O(n²)

def bubble(a):
    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

Флаг swapped даёт лучший случай O(n) на почти отсортированных данных — это тот нюанс, который отличает «реализовал» от «понимаю».

Вставками — O(n²), но быстрая на практике

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

На массивах до ~50 элементов обгоняет быструю сортировку из-за малых констант, поэтому промышленные сортировки переключаются на неё для коротких подмассивов.

Быстрая (quicksort) — O(n log n) в среднем

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left  = [x for x in a if x < pivot]
    mid   = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quicksort(left) + mid + quicksort(right)

Слиянием (merge sort) — гарантированные O(n log n)

def merge_sort(a):
    if len(a) <= 1:
        return a
    m = len(a) // 2
    l, r = merge_sort(a[:m]), merge_sort(a[m:])
    res, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            res.append(l[i]); i += 1
        else:
            res.append(r[j]); j += 1
    return res + l[i:] + r[j:]

Сравнительная таблица

Что такое устойчивость и зачем она

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