Лекция. Сортировки. Инварианты циклов
Лекция 3. Сортировки. Инварианты циклов
На лекции 2 мы оценивали время как функцию от размера входа. Сегодня другой вопрос: что значит «упорядочить» и как доказать, что цикл сортировки делает именно это.
Вставки, выбор, подсчёт и LSD в полный цикл соберёте на семинаре 3. Здесь — постановка, флаг и замер наивных циклов, картинки инвариантов и почему сравнениями быстрее $n\log n$ нельзя.
План
- Отношение порядка. Камень-ножницы-бумага. Чем сортировка отличается от раскладывания по корзинам.
- Проверка флагом, обезьяна, один прогон, Fool.
- Пузырёк: тот же обмен, но прогон до конца; инвариант как
assert. - Вставки и выбор — две картинки.
- Нижняя оценка $\Omega(n\log n)$ и сортировка подсчётом. Устойчивость и ключ.
- Поразрядная LSD (карточки).
- Домашнее задание: короткий текст в LaTeX.
Отношение порядка
Говорят, что на множестве задано отношение порядка, если для любой пары элементов $a$, $b$ истинно ровно одно из трёх:
$$ a > b,\qquad a < b,\qquad a = b, $$
и сравнение транзитивно: если $a > b$ и $b > c$, то $a > c$.
Тогда у конечного непустого множества есть наибольший элемент, «пройтись по возрастанию» осмысленно, а алгоритм может опираться на сравнения.
Если хотя бы одно из условий ломается, слово «максимум» уже не означает то, что мы привыкли.
Камень, ножницы, бумага
Массив [Камень, Ножницы, Бумага]. Можно ли найти «максимум» по обычным правилам игры?
Камень бьёт ножницы, ножницы — бумагу, бумага — камень. Получается цикл, а не порядок: транзитивность не выполняется, «самого сильного» нет.
Это про правила игры, не про числа с плавающей точкой. Сломанное сравнение float('nan') — другая история, её разберёте на семинаре.
beats = {
"камень": "ножницы",
"ножницы": "бумага",
"бумага": "камень",
}
def wins(a, b):
return beats[a] == b
print("камень бьёт ножницы:", wins("камень", "ножницы"))
print("ножницы бьют бумагу:", wins("ножницы", "бумага"))
print("транзитивность требовала бы, что камень бьёт бумагу:",
wins("камень", "бумага"))
print("наоборот, бумага бьёт камень:", wins("бумага", "камень"))
Сортировка — не корзины
В быту «посортировать бельё» часто значит разложить по корзинам: белое отдельно, цветное отдельно. Это группировка. Внутри корзины порядок позиций не задан.
В курсе сортировка — получить неубывающий или невозрастающий порядок позиций: каждый следующий элемент не меньше (или не больше) предыдущего.
Группировку мы уже встречали как частотный массив: индекс — значение. Сортировка подсчётом позже воспользуется такой сводкой, но цель всё равно — порядок позиций, не просто кучки.
Что можно упорядочить
Нужны две вещи.
- Элементы лежат во множестве, на котором сравнение осмысленно и согласовано (как в начале лекции). Строки — да, если фиксирован алфавитный порядок. Камень-ножницы-бумага — нет.
- Есть изменяемая структура с позициями, куда этот порядок можно записать. Обычно это массив (
list).
Неизменяемый кортеж «сортировать на месте» нельзя: позиций не переставить. Можно построить новый список — это уже другая структура.
a = [3, 1, 2]
a[0], a[1] = a[1], a[0]
print("список после обмена:", a)
t = (3, 1, 2)
t[0], t[1] = t[1], t[0]
Проверка за один проход
Достаточно соседних пар. Если хоть одна пара нарушает неубывание, массив не упорядочен.
Идея: флаг (is_ascending), один проход слева направо. Пока всё в порядке, флаг истинный; нашли инверсию — флаг ложный. Даже если цикл доходит до конца, ответ уже есть: предикат «упорядочен?» готов для while not ….
Пар $n-1$, время $\Theta(n)$. Пустой массив и массив из одного элемента соседних пар не дают: нарушать нечему. Знак сравнения важен: $a_i \le a_{i+1}$ — неубывание, $a_i < a_{i+1}$ — строгий рост.
def is_ascending(a):
flag = True
for i in range(0, len(a) - 1):
if a[i] > a[i + 1]:
flag = False
return flag
print([1, 2, 2, 4], is_ascending([1, 2, 2, 4]))
print([1, 3, 2, 4], is_ascending([1, 3, 2, 4]))
Обезьяна и комбинаторный взрыв
Monkey sort: пока флаг не сказал «готово» — перемешать массив наугад.
Цикл пишется в несколько строк, и сразу видно, зачем это ярлык, а не метод курса. Ожидаемое число попыток растёт как $n!$: комбинаторный взрыв. На $n = 10$ уже миллионы перемешиваний, дальше ждать бессмысленно. Таблица факториалов ниже — объяснение тех же чисел, не отдельная теория.
Полный перебор перестановок мёртв так же, как полный перебор кандидатов-делителей на $x \sim 10^9$ с лекции 2: пространство ответов слишком велико.
import random
n = 10
A = list(range(n))
random.shuffle(A)
print(A)
def monkey_sort(A: list):
n = 0
while not is_ascending(A):
random.shuffle(A)
n += 1
print(n)
monkey_sort(A)
print(A)
from time import perf_counter
for n in range(1, 15):
t = perf_counter()
A = list(range(n, 0, -1))
monkey_sort(A)
print('\t', perf_counter() - t)
from math import factorial
for n in (5, 8, 10, 12):
print(n, factorial(n))
Один прогон не сортирует
Та же петля, что у проверки, но в if a[i] > a[i+1] меняем соседей местами.
На обратно упорядоченном массиве после одного прохода максимум оказывается в конце, а префикс остаётся перевёрнутым: [12, …, 1] становится [11, …, 1, 12]. Что-то всплыло, массив целиком не собрался. На трёх числах то же самое: [2, 3, 1] → [2, 1, 3].
Один прогон — это ещё не сортировка.
a = list(range(n, 0, -1))
print("до: ", a)
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
print("после:", a)
Fool: повторять прогон
Fool sort — чинить соседнюю инверсию и не усложнять себе жизнь. В записи ниже один индекс: идём вправо, на обмене возвращаемся в начало. Вложенного for нет.
За это приходится платить. Каждый обмен заставляет заново просмотреть префикс, и на обратно упорядоченном входе число сравнений растёт уже как куб — отсюда кривая рядом с $n^3$. Отсутствие вложенных циклов не гарантия даже квадрата, тем более линейности.
Вывод, мост к лекции 2: смотрите на число операций, не на «сколько for в тексте». На больших $n$ такая наивность даёт TLE.
def fool_sort(a: list):
i = 0
n = 0
while i < len(a) - 1:
n += 1
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
i = 0
else:
i += 1
return n
num_op = []
for n in range(1, 40):
a = list(range(n, 0, -1))
num_op.append(fool_sort(a))
print(*range(1, 40), sep='\t')
print(*num_op, sep='\t')
import matplotlib.pyplot as plt
x = range(1, 40)
x3 = [0.18*i**3 for i in x]
plt.plot(x, num_op, x, x3)
Пузырёк и инвариант
Пузырёк — те же соседние обмены, но прогон доводят до конца и помнят флагом, был ли обмен. Индекс после инверсии в начало не сбрасывают. На графике это уже не куб: в худшем случае $\Theta(n^2)$ сравнений. Проход без обменов — «готово».
Держим один вариант инварианта: после $k$ проходов $k$ наибольших уже стоят на своих местах справа, в порядке. Следующий прогон достаточно вести только по ещё не зафиксированному префиксу.
Инвариант
Инвариант цикла — утверждение, которое верно на границе итерации. Его можно мысленно поставить как assert.
Для пузырька после $k$ проходов:
суффикс длины $k$ содержит $k$ наибольших элементов массива и сам упорядочен.
Отсюда видно, зачем хватает $n-1$ проходов: когда $k = n-1$, слева остался один элемент, и он обязан быть наименьшим.
def bubble_sort(a: list):
n = 0
is_ascending = False
while not is_ascending:
is_ascending = True
for i in range(len(a) - 1):
n += 1
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
is_ascending = False
return n
num_op2 = []
for n in x:
a = list(range(n, 0, -1))
num_op2.append(bubble_sort(a))
plt.plot(x, num_op2, x, num_op)
Вставки и выбор
Две картинки, не два доказательства. Оба в худшем случае $\Theta(n^2)$ сравнений. Вставки обычно дешевле на почти упорядоченном входе: новый элемент почти никуда не едет. Выбор адаптивным не бывает: он каждый раз смотрит весь хвост.
Доказать корректность одного из двух (какой — решает монетка) — домашнее задание к лекции. Код туда не пишите. Полные циклы — на семинаре; здесь только один шаг, чтобы было видно инвариант.
Выбор
Инвариант (один, его и держим): префикс длины $k$ содержит $k$ наименьших элементов массива.
Каждый шаг: в хвосте находим минимум и меняем его с элементом на границе префикса. Префикс удлиняется на единицу.
Вставки
Инвариант: префикс длины $k$ уже упорядочен.
Новый элемент «въезжает» на своё место сдвигами вправо тех, кто больше него. Префикс снова упорядочен, только длиннее.
a = [4, 1, 3, 2]
print("выбор, до шага: ", a)
j = 1 # минимум хвоста [4, 1, 3, 2] стоит на месте 1
a[0], a[j] = a[j], a[0]
print("выбор, префикс k=1:", a)
a = [4, 1, 3, 2]
print("вставки, до шага: ", a)
# префикс [4] упорядочен; 1 въезжает, 4 сдвигается вправо
a[1] = a[0]
a[0] = 1
print("вставки, префикс k=2:", a)
Нижняя оценка в модели сравнений
Представим, что алгоритм умеет только спрашивать «$a_i < a_j$?» и ветвиться по ответу. Каждая перестановка входа — отдельный лист в дереве таких вопросов: иначе два разных порядка получили бы один и тот же ответ.
Листьев нужно не меньше $n!$. Высота дерева (число вопросов в худшем случае) не меньше $\log_2(n!)$. По формуле Стирлинга это $\Omega(n\log n)$. Вывод Стирлинга не разбираем: достаточно «логарифм факториала растёт как $n\log n$».
Следствия:
- пузырёк, вставки, выбор в этой модели не оптимальны по порядку: они $n^2$, а нижняя оценка только $n\log n$; Fool в записи выше ещё хуже, куб;
- сравнениями быстрее $n\log n$ в худшем случае нельзя;
- подсчёт в эту модель не входит: он не спрашивает «$a_i < a_j$?», а использует, что ключ — небольшое целое и годится как индекс.
from math import factorial, log2
for n in (4, 8, 16):
print(
n,
" n! =", factorial(n),
" log2(n!) ≈", round(log2(factorial(n)), 1),
" n log2 n ≈", round(n * log2(n), 1),
)
Сортировка подсчётом
Если ключи — целые из известного малого диапазона (например, от $0$ до $U$), индекс массива снова может значить значение, как частотный массив на семинаре 2.
Сначала сводка: сколько раз встретился каждый ключ $v$. Затем выписывание: значение $v$ повторяем столько раз, сколько насчитали. На доске достаточно этой картинки; цикл выписывания соберёте на семинаре.
Время $\Theta(n + U)$. Путать $n$ и $U$ нельзя: длина входа и размер диапазона — разные величины. Если $U$ порядка $10^9$, массив частот не построите.
a = [3, 1, 3, 2, 1, 3]
U = 4 # ключи 0, 1, 2, 3
cnt = [0] * U
for x in a:
cnt[x] += 1
print("вход: ", a)
print("сводка:", cnt)
print("ключ 1 встретился", cnt[1], "раза")
Устойчивость и ключ
Устойчивость: элементы с равными ключами остаются в том же относительном порядке, что и во входе.
Она нужна, когда у равных ключей есть полезная нагрузка (имя, исходный индекс) и когда следующий проход не должен ломать предыдущий — именно так складывают стопку в LSD.
Ключ — то, по чему сравнивают. Это не обязательно весь элемент: у пары $(k, p)$ ключом может быть только $k$. Если сравнивать пары целиком, нагрузка $p$ вмешается.
# (ключ, имя). При равном ключе имена должны идти как во входе.
pairs = [(2, "Боря"), (1, "Аня"), (2, "Вика"), (1, "Гена")]
print("вход: ", pairs)
# устойчиво по ключу: Аня раньше Гены, Боря раньше Вики — как во входе
stable = [(1, "Аня"), (1, "Гена"), (2, "Боря"), (2, "Вика")]
print("устойчиво:", stable)
# ключи те же, но пары с ключом 2 переставлены — устойчивость сломана
broken = [(1, "Аня"), (1, "Гена"), (2, "Вика"), (2, "Боря")]
print("сломано: ", broken)
Поразрядная LSD
LSD (least significant digit) удобнее показывать карточками с дырками и палочкой, чем циклом. Палочка в разряд отделяет «0» и «1»; стопку складывают устойчиво: кто был раньше при равной дырке, тот раньше и остаётся. Так работали табуляторы начала XX века.
Каждый проход — устойчивый подсчёт (или такая стопка) по одной цифре, начиная с младшей. Инвариант после $k$ проходов: порядок правильный по $k$ младшим разрядам.
Не обещаем MSD и «построим radix на следующей неделе». Цикл LSD — на семинаре, если останется время. Ячейка ниже — тот же приём на трёх битах, не замена карточкам. Подробный разбор (псевдокод, инвариант, время и память) — в lsd-example.tex.
# четыре числа в трёх битах: 5=101, 2=010, 7=111, 4=100
nums = [5, 2, 7, 4]
print("биты: ", [(x, format(x, "03b")) for x in nums])
# проход по младшему биту, устойчиво: сначала все *0 в старом порядке, потом *1
zeros = [x for x in nums if x % 2 == 0]
ones = [x for x in nums if x % 2 == 1]
after = zeros + ones
print("после младшего бита:", after, [format(x, "03b") for x in after])
print("инвариант: младший бит уже в порядке 0,0,1,1")
Домашнее задание
Короткий текст в LaTeX: монетка выбирает вставки или выбор. Условие, шаблон и образец — на отдельной странице:
https://learn.ai.msu.ru/algo/1/03/hw-lecture/
Сдаёте лектору .tex и PDF, не семинаристу.