Неделя 5

Семинар. Разделяй и властвуй: merge sort и quick sort

скачать .ipynb

Семинар 5. Разделяй и властвуй: merge sort и quick sort

Лекция 5 дала слияние, сортировку слиянием, разбиения Ломуто и Хоара, худший случай и случайный опорный. Здесь вы пишете это руками: сначала слияние, потом сортировку слиянием, потом разбиение и быструю сортировку.

Встроенную сортировку сегодня не используем как решение. sorted() и a.sort() допустимы только как эталон проверки: с ними сравниваем свой результат. Это условие пары, а не ограничение тестера.

Ноутбук — тетрадь пары. Его семинаристу не отправляйте. Зачёт пары — прорешанность задач контеста на algo.ai.msu.ru.

Заглушки ничего не сортируют и возвращают неверный ответ — так и задумано, их надо переписать.

Как устроен ноутбук

Как на семинарах 1–4: ячейки Markdown и Code; командный режим — Esc, правка — Enter; Shift+Enter выполняет ячейку.

Скачайте с сайта курса этот файл .ipynb. Отдельного файла тестов на этой неделе нет: проверки встроены в ноутбук, зачёт — контест на платформе.

Ячейки с комментарием «Ваш эксперимент» никто автоматически не проверяет.

Порядок работы

Номера в заголовках разделов соответствуют этому списку:

  • инструменты проверки: is_sorted, check_sort, check_pairs_sort, check_partition;
  • 1. слияние двух упорядоченных массивов;
  • 2. сортировка слиянием и устойчивость по ключу;
  • 3. разбиение Ломуто и проверка его контракта;
  • 4. быстрая сортировка: границы рекурсии, глубина на плохом входе, случайный опорный;
  • 5. почему quick sort неустойчив — и чем контракт Хоара отличается от Ломуто;
  • 6. трёхчастное разбиение (нужно для задачи № 6); quickselect и подсчёт инверсий — по желанию;
  • контест на algo.ai.msu.ru.

Разделы 1–5 — основная часть пары. В разделе 6 трёхчастное разбиение нужно для обязательной задачи № 6, остальное — по желанию.

Инструменты проверки

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

Здесь sorted() стоит внутри проверки, а не внутри решения: сравнивать свой ответ с эталоном — нормальная практика, сдавать эталон вместо решения — нет.

In [ ]:
import random


def is_sorted(a):
    """Массив неубывает?"""
    return all(a[i] <= a[i + 1] for i in range(len(a) - 1))


def check_sort(sort_fn, in_place=False, trials=200, seed=0):
    """Проверяет сортировку на случайных массивах; sorted() — только эталон.

    seed фиксирован, поэтому неудача воспроизводится: набор входов один и тот же.
    """
    rng = random.Random(seed)
    for _ in range(trials):
        a = [rng.randint(-5, 5) for _ in range(rng.randint(0, 12))]
        expected = sorted(a)
        if in_place:
            got = a[:]
            sort_fn(got)
        else:
            got = sort_fn(a[:])
        if got != expected:
            print("не сходится на", a)
            print("  получено: ", got)
            print("  ожидается:", expected)
            return False
    print(f"ok: {trials} случайных массивов отсортированы верно")
    return True


def check_pairs_sort(sort_pairs_fn, trials=200, seed=0):
    """Сортировка пар по ключу и её устойчивость.

    Эталон — sorted с ключом x[0]: встроенная сортировка устойчива, поэтому
    пары с равными ключами обязаны остаться в порядке входа.
    """
    rng = random.Random(seed)
    for _ in range(trials):
        keys = [rng.randint(0, 3) for _ in range(rng.randint(0, 10))]
        payload = list(range(len(keys)))
        rng.shuffle(payload)
        pairs = list(zip(keys, payload))
        expected = sorted(pairs, key=lambda x: x[0])
        got = sort_pairs_fn(pairs[:])
        if got != expected:
            print("не сходится на", pairs)
            print("  получено: ", got)
            print("  ожидается:", expected)
            print("  подсказка: сравнивайте ключ x[0], а не пару целиком")
            return False
    print(f"ok: {trials} наборов пар отсортированы устойчиво по ключу")
    return True


print("инструменты готовы")

1. Слияние двух упорядоченных массивов

Два уже неубывающих массива left и right. Держим два указателя на первые ещё не взятые элементы. Меньшую голову переносим в результат и сдвигаем её указатель. Когда один массив кончился, дописываем остаток другого.

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

Равные ключи. При равенстве берите из левого массива: left[i] <= right[j]. На этом стоит устойчивость сортировки слиянием.

Время — линейное от суммы длин. Обратите внимание на пустые массивы: отдельной ветки для них быть не должно, цикл просто не сделает ни шага.

In [ ]:
def merge(left, right):
    """Слияние двух неубывающих массивов в новый неубывающий массив."""
    return []


print(merge([1, 4, 7], [2, 4, 8]))  # ожидается [1, 2, 4, 4, 7, 8]
print(merge([], [1, 2]))            # ожидается [1, 2]
print(merge([3], []))               # ожидается [3]
print(merge([1, 2, 3], [4, 5]))     # ожидается [1, 2, 3, 4, 5]
In [ ]:
# Ваш эксперимент: сколько сравнений делает слияние в лучшем и худшем случае?
# Добавьте счётчик и проверьте на [1, 2, 3] + [4, 5, 6] и на [1, 3, 5] + [2, 4, 6].

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

Рекурсивная схема ровно с лекции:

  • база — ноль или один элемент, такой массив уже упорядочен;
  • шаг — разрезать пополам, отсортировать половины тем же способом, слить.
        [5 1 4 2 | 8 3 7 6]
       /                   \
   [5 1 4 2]             [8 3 7 6]
    /     \               /     \
 [5 1]   [4 2]        [8 3]   [7 6]

Сначала полностью завершается левый вызов, затем правый, и только потом слияние. На каждом уровне суммарно линейная работа, уровней $\Theta(\log n)$, итого $\Theta(n\log n)$ — всегда, в том числе на уже отсортированном входе.

Версия ниже возвращает новый список и не портит вход. Срезы a[:m] и a[m:] копируют данные: это те самые $\Theta(n)$ дополнительной памяти.

In [ ]:
def merge_sort(a):
    """Новый неубывающий список из элементов a; вход не меняется."""
    return []


print(merge_sort([5, 1, 4, 2, 8, 3, 7, 6]))  # ожидается [1, 2, 3, 4, 5, 6, 7, 8]
print(merge_sort([]), merge_sort([7]))        # ожидается [] [7]

original = [3, 1, 2]
merge_sort(original)
print(original)  # ожидается [3, 1, 2] — вход не испорчен

check_sort(merge_sort)

Устойчивость по ключу

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

Сравнивайте именно ключ, x[0], а не пару целиком. Если сравнить пары целиком, порядок равных ключей задаст нагрузка — это уже другая задача.

In [ ]:
def merge_sort_pairs(pairs):
    """Сортировка пар (ключ, нагрузка) по ключу; при равных ключах порядок как во входе."""
    return []


print(merge_sort_pairs([(2, "a"), (1, "c"), (2, "b")]))
# ожидается [(1, 'c'), (2, 'a'), (2, 'b')] — 'a' раньше 'b', как во входе

print(merge_sort_pairs([(5, "x"), (5, "y"), (5, "z")]))
# ожидается [(5, 'x'), (5, 'y'), (5, 'z')] — порядок не меняется

print(merge_sort_pairs([(2, "b"), (1, "c"), (2, "a")]))
# ожидается [(1, 'c'), (2, 'b'), (2, 'a')]
# если вышло [(1, 'c'), (2, 'a'), (2, 'b')] — пары сравниваются целиком, а не по ключу

check_pairs_sort(merge_sort_pairs)

3. Разбиение Ломуто

Работаем с полуинтервалом [l, r) внутри массива, на месте. Опорный элемент — последний в диапазоне: pivot = a[r-1].

Перед обработкой позиции j держим четыре зоны:

ЗонаЧто там
[l, i)элементы < pivot
[i, j)элементы >= pivot
[j, r-1)ещё не просмотрены
a[r-1]сам опорный

Шаг: если a[j] < pivot, меняем a[i] и a[j] и увеличиваем i. В конце меняем a[i] и a[r-1] — опорный встаёт на окончательную позицию p = i, которую возвращаем.

Сравнение строгое <. Разбиение — это ещё не сортировка: обе части могут остаться неупорядоченными.

Пример с лекции: [4, 1, 6, 3, 2, 5] превращается в [4, 1, 3, 2, 5, 6], p = 4.

In [ ]:
def partition_lomuto(a, l, r):
    """Разбивает a[l:r] по опорному a[r-1]; возвращает окончательную позицию опорного."""
    return -1


a = [4, 1, 6, 3, 2, 5]
p = partition_lomuto(a, 0, len(a))
print(a, "p =", p)  # ожидается [4, 1, 3, 2, 5, 6] p = 4

Проверка контракта

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

In [ ]:
def check_partition(partition_fn, trials=200, seed=0):
    """Проверяет контракт разбиения на случайных массивах.

    seed фиксирован, поэтому неудача воспроизводится.
    """
    rng = random.Random(seed)
    for _ in range(trials):
        a = [rng.randint(-5, 5) for _ in range(rng.randint(1, 12))]
        b = a[:]
        p = partition_fn(b, 0, len(b))
        if not isinstance(p, int) or not 0 <= p < len(b):
            print("позиция вне диапазона:", a, "->", b, "p =", p)
            return False
        pivot = b[p]
        if sorted(b) != sorted(a):
            print("элементы потеряны:", a, "->", b)
            return False
        if any(x >= pivot for x in b[:p]) or any(x < pivot for x in b[p + 1:]):
            print("контракт нарушен:", a, "->", b, "p =", p)
            return False
    print(f"ok: контракт держится на {trials} массивах")
    return True


check_partition(partition_lomuto)

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

Опорный уже стоит на своём месте, поэтому его позиция в рекурсивные вызовы не входит:

def quick_sort(a, l, r):
    if r - l <= 1:
        return
    p = partition_lomuto(a, l, r)
    quick_sort(a, l, p)
    quick_sort(a, p + 1, r)

Диапазоны [l, p) и [p+1, r) строго короче родительского даже при крайнем p — поэтому рекурсия заканчивается.

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

In [ ]:
max_depth = 0


def quick_sort(a, l, r, depth=0):
    """Сортирует a[l:r] на месте разбиением Ломуто; depth — только для замера глубины."""
    global max_depth
    max_depth = max(max_depth, depth)
    return None


b = [4, 1, 6, 3, 2, 5]
quick_sort(b, 0, len(b))
print(b)  # ожидается [1, 2, 3, 4, 5, 6]

check_sort(lambda x: quick_sort(x, 0, len(x)), in_place=True)

Плохой вход и глубина рекурсии

У Ломуто с последним опорным элементом уже отсортированный массив различных чисел даёт вырожденное дерево: каждое разбиение отделяет один элемент, глубина растёт как $n$, а работа — как $n^2$.

Ячейка ниже сравнивает случайный вход и отсортированный на $n = 500$. Ожидаемый порядок величин: у случайного глубина — десятки, у отсортированного — около 500.

Отсюда практическое следствие: на $n$ в несколько тысяч такой вход упрётся в лимит глубины рекурсии Python и вы получите RecursionError вместо результата.

In [ ]:
n = 500
inputs = {
    "случайный": [random.randint(0, 10 ** 6) for _ in range(n)],
    "уже отсортированный": list(range(n)),
}

for name, data in inputs.items():
    max_depth = 0
    b = data[:]
    quick_sort(b, 0, len(b))
    print(f"{name}: глубина {max_depth}, отсортирован: {is_sorted(b)}")

# Ваш эксперимент: добавьте вход list(range(n, 0, -1)) — массив, упорядоченный по убыванию.
# Предскажите глубину до запуска.

Случайный опорный элемент

Лечится не сам худший случай, а его привязка к конкретному входу: перед разбиением выбираем случайный индекс в [l, r) и меняем этот элемент с последним. Дальше — то же разбиение Ломуто.

Для различных ключей ожидаемое время становится $\Theta(n\log n)$ на любом фиксированном входе, но худший случай остаётся квадратичным: он просто перестаёт достигаться отсортированным массивом.

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

In [ ]:
n = 500          # тот же размер, что выше, но задан локально: ячейку можно запускать отдельно


def quick_sort_random(a, l, r, depth=0):
    """То же, но опорный выбирается случайно и переносится в конец перед разбиением."""
    global max_depth
    max_depth = max(max_depth, depth)
    return None


check_sort(lambda x: quick_sort_random(x, 0, len(x)), in_place=True)

for name, data in (("уже отсортированный", list(range(n))),
                   ("все элементы равны", [7] * n)):
    max_depth = 0
    b = data[:]
    quick_sort_random(b, 0, len(b))
    print(f"{name}: глубина {max_depth}, отсортирован: {is_sorted(b)}")

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

5. Почему quick sort неустойчив

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

Контрпример с лекции: пары (2, 'a'), (2, 'b'), (1, 'c'). Одно разбиение Ломуто уже переставляет 'a' и 'b' местами.

In [ ]:
# partition_lomuto сравнивает элементы целиком. Здесь все сравнения идут между
# разными ключами (2 и 1), поэтому результат тот же, что при сравнении только ключа.
pairs = [(2, "a"), (2, "b"), (1, "c")]
p = partition_lomuto(pairs, 0, len(pairs))
print(pairs, "p =", p)
# ожидается [(1, 'c'), (2, 'b'), (2, 'a')] p = 0
# ключи упорядочены верно, но 'b' оказалась раньше 'a' — устойчивость сломана

6. По желанию и для контеста

Три упражнения. Трёхчастное разбиение нужно для обязательной задачи № 6 (75. Sort Colors) — идею разберём у доски, код пишете сами. quickselect (№ 7) и подсчёт инверсий (№ 9) — по желанию, для зачёта не требуются.

Трёхчастное разбиение — нужно для № 6

Лекция упоминала проблему одинаковых ключей: Ломуто на массиве равных значений вырождается. Лечение — разбить сразу на три части: < pivot, = pivot, > pivot. Тогда все равные опорному уходят из рекурсии за один проход.

Держим три границы и идём по массиву один раз: lt — конец зоны меньших, i — текущая позиция, gt — начало зоны больших. Функция возвращает пару (lt, gt): равные опорному занимают полуинтервал [lt, gt).

In [ ]:
def partition_three(a, pivot):
    """Переставляет a на месте: сначала < pivot, потом = pivot, потом > pivot.

    Возвращает (lt, gt): равные опорному лежат в полуинтервале [lt, gt).
    """
    return (-1, -1)


b = [2, 0, 2, 1, 1, 0]
print(partition_three(b, 1), b)  # ожидается (2, 4) [0, 0, 1, 1, 2, 2]

★ Порядковая статистика без полной сортировки

Разбиение даёт больше, чем сортировку. После него опорный стоит на окончательной позиции p. Если нужен элемент, который в упорядоченном массиве стоял бы на позиции k, то:

  • p == k — это и есть ответ;
  • p > k — ответ слева, продолжаем в [l, p);
  • p < k — ответ справа, продолжаем в [p+1, r).

Рекурсивный вызов нужен только один — как в бинарном поиске. Поэтому в среднем работа линейная, а не $n\log n$: полностью сортировать массив не требуется.

In [ ]:
def kth_smallest(a, k):
    """Элемент, который стоял бы на позиции k (от нуля) в упорядоченном a; вход не менять."""
    return -1


data = [3, 2, 1, 5, 6, 4]
print([kth_smallest(data, k) for k in range(len(data))])  # ожидается [1, 2, 3, 4, 5, 6]
print(data)  # ожидается [3, 2, 1, 5, 6, 4] — вход не испорчен

# В задаче № 7 (215) просят k-й наибольший, и k там с единицы:
# ответ — kth_smallest(a, len(a) - k).

★ Слияние считает больше, чем сортирует

Инверсия — пара индексов $i < j$, для которой $a[i] > a[j]$. Число инверсий показывает, насколько массив далёк от упорядоченного: у отсортированного их ноль, у развёрнутого — максимум.

Двойным циклом это $\Theta(n^2)$. Но слияние уже знает ответ: когда вы берёте элемент из правой половины, он меньше всех оставшихся в левой — а значит, образует инверсию с каждым из них сразу. Добавьте к счётчику число оставшихся в левой половине.

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

In [ ]:
def count_inversions(a):
    """Число пар i < j с a[i] > a[j]; вход не менять."""
    return -1


print(count_inversions([2, 4, 1, 3, 5]))  # ожидается 3
print(count_inversions([1, 2, 3]))        # ожидается 0
print(count_inversions([3, 2, 1]))        # ожидается 3
print(count_inversions([]))               # ожидается 0

Контест

Задачи сдавайте в контест недели 5 на algo.ai.msu.ru. Номера LeetCode помогают найти условие.

Для зачёта семинара обязательны № 5 (912. Sort an Array) и № 6 (75. Sort Colors). Разминка и задачи по желанию их не заменяют.

№ЗадачаСтатус на семинареЧто из ноутбука
188. Merge Sorted ArrayРазминкаmerge; здесь его просят сделать на месте, с конца
2977. Squares of a Sorted ArrayРазминкато же слияние, только две монотонные части нужно сначала увидеть
3283. Move ZeroesРазминкацикл Ломуто: указатель записи и указатель просмотра
4905. Sort Array By ParityРазминкаразбиение по предикату; сравните схему Ломуто и встречные указатели
5912. Sort an ArrayОбязательнаяmerge_sort — рабочий вариант; quick_sort годится на различных ключах
675. Sort ColorsОбязательнаяpartition_three за один проход
7215. Kth Largest Element in an ArrayПо желаниюkth_smallest; сортировка проходит тесты, но на паре нужен quickselect
856. Merge IntervalsПо желаниюсортировка как подготовка к линейному проходу
9493. Reverse Pairs ★По желаниюcount_inversions; условие считает пары с $a[i] > 2\cdot a[j]$

Порядок работы. Разминку № 1–4 закрывайте быстро, они на один приём каждая. Главная задача пары — № 5: в ней встроенную сортировку использовать нельзя по условию, и именно там пригодится случайный опорный. Дальше № 6. Остальное — по желанию и дома.

Типичный WA: при равенстве в слиянии берут из правой половины и теряют устойчивость; в Ломуто сравнивают нестрого; опорный оставляют в одном из рекурсивных диапазонов; в трёхчастном разбиении сдвигают i после обмена с зоной больших.

Типичный TLE и RecursionError: quick sort с последним опорным на отсортированном входе; полная сортировка там, где нужна одна порядковая статистика; пересборка списков срезами внутри цикла.

Про встроенную сортировку. В № 5 (912) она запрещена условием самой задачи. В № 8 (56) сортировка — только подготовительный шаг: там sorted() допустим и решением не считается. В проверках ноутбука sorted() — эталон.

Про № 5 и глубину рекурсии. В 912 длина массива до 5·10⁴. Уже отсортированный вход с последним опорным даёт вырожденное дерево и RecursionError (лимит Python около 1000). Рабочий рецепт — merge sort: $\Theta(n\log n)$ на любом входе и глубина $\Theta(\log n)$. Поднимать sys.setrecursionlimit под Ломуто не стоит: на различных ключах случайный опорный и так даёт глубину порядка логарифма, а на одинаковых ключах Ломуто по-прежнему отделяет один элемент — глубина около $n$ и время $\Theta(n^2)$, так что вместо RecursionError будет превышение по времени.

Шпаргалка

Слияние и merge sort:

  • смотрим только две головы; при равенстве берём слева — это устойчивость;
  • база рекурсии — ноль или один элемент;
  • $\Theta(n\log n)$ всегда, в том числе на отсортированном входе;
  • пиковая дополнительная память $\Theta(n)$, глубина $\Theta(\log n)$.

Разбиение и quick sort:

  • Ломуто: опорный a[r-1], зоны [l, i) и [i, j), строгое <, в конце опорный на позиции p;
  • позиция p в рекурсивные вызовы не входит: [l, p) и [p+1, r);
  • отсортированный вход + последний опорный = вырожденное дерево, $\Theta(n^2)$ и глубина $n$;
  • случайный опорный даёт ожидаемое $\Theta(n\log n)$ при различных ключах, но не гарантию в худшем случае;
  • одинаковые ключи лечит трёхчастное разбиение, а не рандомизация;
  • разбиение на месте — это $O(1)$ памяти у разбиения, но не у всей сортировки: остаётся стек вызовов;
  • обычные разбиения неустойчивы.

Контракт Хоара (спросят на коллоквиуме):

  • Ломуто возвращает окончательную позицию опорного p: рекурсия на [l, p) и [p+1, r), опорный в вызовы не входит;
  • Хоар возвращает границу b, причём l < b < r: опорный не обязан стоять на месте, рекурсия на [l, b) и [b, r), обе части непусты.

Контест: № 5 (912) — до 5·10⁴ элементов. Рабочий рецепт — merge sort: $\Theta(n\log n)$ и глубина $\Theta(\log n)$; поднимать лимит рекурсии под Ломуто бессмысленно — на одинаковых ключах он даёт глубину около $n$ и время $\Theta(n^2)$.

Сдача

  • Этот .ipynb семинаристу отправлять не нужно.
  • Для зачёта выполните № 5 — 912. Sort an Array и № 6 — 75. Sort Colors в контесте на algo.ai.msu.ru.
  • Разминка № 1–4 и задачи № 7–9 выполняются по желанию, для зачёта не требуются.
  • Если обязательные задачи не закончены на паре, дорешайте их в том же контесте после занятия.
  • На неделе 6 — коллоквиум по лекциям 1–5. Слияние, merge sort, разбиение Ломуто и Хоара, худший случай и память входят в программу; спросят и трассировку на маленьком массиве.