Простые сортировки: пузырьком, выбором, вставками

Правило пузырька: сравнивать можно только соседей и менять их местами при нарушении порядка.

Если идти слева направо, максимум выигрывает каждое следующее сравнение и уезжает в конец. Значит, после одного прохода максимальный элемент стоит на своём месте. Проходов нужно N − 1, и каждый следующий короче на i: готовый хвост перепроверять незачем.

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

a = [5, 1, 4, 2, 8, 3]
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

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

Ловушки:

• range(n) вместо range(n - 1 - i) – на последней паре a[j + 1] вылезет за конец списка, программа упадёт с IndexError.
• >= вместо > – лишние обмены на равных элементах и потеря устойчивости.

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

Обмен – не больше одного на шаг, шагов N − 1; если минимум уже на месте, обмен пропускается. А сравнений – $N \cdot (N-1)/2$ в любом случае: поиск минимума всегда просматривает весь остаток, даже если список уже упорядочен.

a = [5, 1, 4, 2, 8, 3]
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
    if m != i:
        a[i], a[m] = a[m], a[i]

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

Выбор неустойчив: обмен через голову переставляет элемент сразу через полсписка и может перескочить через равного ему.

Так раскладывают карты в руке: очередную карту вынимают и сдвигают влево, пока левый сосед больше неё.

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

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

a = [5, 1, 4, 2, 8, 3]
n = len(a)

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

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

Порядок условий в while важен: если j стал −1, проверять a[j] > key уже нельзя. Python вычисляет and слева направо и до второй части не доходит, когда первая ложна.

В худшем случае все три делают порядка $N \cdot (N-1)/2$ сравнений: для N = 6 это 15, для 1000 – около полумиллиона. Разница – в обменах и в поведении на готовых данных.

Замер на 8 000 случайных чисел, Python 3.12: пузырёк 3,858 с, выбор 0,998 с, вставки 1,00 с. При удвоении N время каждого растёт примерно вчетверо – все три относятся к $O(N^2)$.

Вставки на тех же 8 000 элементах, поданных в разном порядке:

Встроенная a.sort() те же 8 000 элементов сортирует за 0,0006 с – об этом урок 10.6.