Погоди, что? GCC std::sort использует квадратичную сортировку вставками? WTF???

Я знаю многих программистов и руководителей в IT компаниях, которые недолюбливают математиков и в частности считают их далёкими от жизни идиотами из-за их утверждений в духе "нельзя отсортировать последовательность быстрее, чем за nlogn" -- ведь это очевидным образом неверно, есть же сортировка подсчетом и radix sort. Нюанс в том, что описанное выше -- это распространённая некорректная трактовка одной из ключевых теорем об алгоритмах сортировок, корректное утверждение выглядит так: "не существует алгоритма, который бы гарантированно находил перестановку n элементов, приводящую к возрастающему порядку, быстрее чем за nlogn используя только операции попарного сравнения". В этом утверждении больше слов, оно более сложно в плане когнитивного восприятия, ключевой момент обозначил жирным шрифтом, чувствуете разницу?

В статье хочу рассказать об этой теореме и ещё о двух, на которые я наткнулся когда вел занятия по информатике в 9-11 классах будучи студентом старших курсов. Эти теоремы для меня были удивительным открытием, радовался вне себя когда вывел сам одну из них - её я не встречал ни в одном учебнике по информатике. В последствии все три теоремы были найдены в недрах Кнута, но чёрт побери, их поиск был сложнее, чем вывод!

Если я ещё не убедил Вас прочитать статью, то вот моя последняя попытка: в статье объясню почему пузырёк -- это бесполезная фигня, но внезапно практически также работающая сортировка вставками -- это супер важная сортировка, являющаяся частью std::sort в MSVC, GCC и Clang. Расскажу, каким интересным свойством оптимальности обладает сортировка выбором, являющаяся в теории такой же неэффективной как пузырёк.

Теорема №1

Здесь никаких сюрпризов -- та самая теорема про nlogn, но всё-таки я её распишу формально, на сначала для полноты картины

Определение 1. Перестановкой порядка n называется последовательность

$p_0, p_1, \ldots, p_{n-1}\in\{0, 1, \ldots, n-1\}~~i\neq j\Rightarrow p_i\neq p_j$

Неформально перестановка -- это взяли 0, 1, ... , n-1 и перемешали. В терминах перестановок удобно изучать свойства алгоритмов сортировок: по сути задача сортировки состоит в том, чтобы найти такую перестановку элементов, которая даёт неубывающий порядок. Теперь мы готовы сформулировать теорему

Не существует универсального алгоритма, который бы для произвольной последовательности длины n

$a_0, a_1, a_2, \ldots, a_{n-1}$

находил бы перестановку элементов p такую, что

$a_{p_0}\leq a_{p_1}\leq \ldots \leq a_{p_{n-1}}$

используя меньше, чем

$\mathcal{O}(n\log n)$

попарных сравнений, т.е. сравнений двух конкретных элементов.

Для доказательства этого утверждения я люблю приводить небольшую аналогию: представьте, что вы играете в игру со своим коллегой. Он загадывает некоторый предмет, а вы задаёте вопрос про этот предмет, подразумевается ответ да/нет. Ваша цель отгадать предмет. Математическая формулировка этой игры примерно такая: есть конечное множество Х, первый игрок выбирает элемент этого множества y, второй может задавать вопросы вида "Правда, что y принадлежит подмножеству A?". Вопрос, который нас будет интересовать -- какая стратегия выбора вопросов/подмножеств для второго игрока приведет к минимальному числу вопросов для гарантированной идентификации y?

Ответ оказывается довольно простым: минимальное количество вопросов, которое нужно задать -- это двоичный логарифм от размера X

$\lceil \log_2|X| \rceil$

Идея простая: когда мы задаём первый вопрос выбрав какое-то подмножество A мы делим X на две части: элементы из A и элементы не из A. Получив ответ от первого игрока вернемся к исходной ситуации, но уже не с множеством X, а с A или X\A (элементы из X исключая элементы из A). Вроде бы интуитивно понятно, что чем больше множество, тем сложнее в этой игре найти конкретный элемент. В худшем случае получив ответ мы останемся с бОльшим по размеру множеством, все что может сделать первый игрок -- это выбрать множество A так, чтобы оно делило X примерно пополам. С этой стратегией мы можем на каждом шаге уменьшать размер множества, в котором есть y в два раза, если быть точнее то все таки размер изменяется так

$n\rightarrow\frac{n+1}{2}$

Когда мы получим множество размера 1, в котором содержится y, будет точно понятно что единственный элемент этого множества -- это y который мы и искали. В итоге имеем следующее: сколько раз множество разера n нужно уполовинить (или если быть точнее уполовинить с округлением вверх), чтобы оно стало размера 1? Это собственно и есть

$\lceil \log_2n\rceil$

Как всё это относится к сортировкам, перестановкам и исходному утверждению? Сравнивая два элемента последовательности мы косвенно делим все возможные перестановки элементов на "правильные" и "неправильные", на такие, где эти два элемента в нужном порядке, и те, где эти два элемента в неправильном порядке. В результате сравнения мы понимаем, что половина перестановок точно неправильные, применяя лоику из описанной выше аналогии -- количество операций сравнения, которое нужно сделать, -- это

$\lceil \log_2n!\rceil$

Наиболее точный способ вычислить это выражение -- это формула Стирлинга, но асимптотическую оценку можно получить например вот так

$\lceil \log_2n!\rceil\geq \left\lceil \log_2\left(\frac{n}{2}\right)^\frac{n}{2}\right\rceil= \left\lceil \frac{n}{2}\log_2\left(\frac{n}{2}\right)\right\rceil=\mathcal{O}(n\log n)$

Теорема №2

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

В такой ситуации внезапно оказывается, что сортировка пузырьком и сортировка вставками делает минимальное число свопов. Если сортировка вставками сделала m свопов на массиве из n элементов, то количество произведенных сравнений не больше n+m-1.

Вот это отличие в поведении делает сортировку пузырьком практически бесполезной, в то время как сортировка вставками используется повсеместно для полноты картины привожу код обеих (код демонстрационный, в проде не использовать)

def bubble_sort(array):
    comparisons = 0
    swaps = 0
    for i in range(len(array) - 1):
        for j in range(len(array) - 1 - i):
            comparisons += 1
            if array[j] > array[j + 1]:
                swaps += 1
                array[j], array[j + 1] = array[j + 1], array[j]
    return comparisons, swaps

def insertion_sort(array):
    comparisons = 0
    swaps = 0
    
    for i in range(0, len(array)):
        j = i
        while j > 0 and array[j - 1] > array[j]:
            comparisons += 1
            swaps += 1
            array[j - 1], array[j] = array[j], array[j - 1]
            j -= 1
        if j > 0:
            comparisons += 1
    return comparisons, swaps

Если прогнать insertion_sort на уже упорядоченном массиве из n элементов, но этот код выдаст n-1 comparisons и 0 swaps. Пузырек же выдаст n(n-1)/2 comparisons, что намного больше.

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

Определение 2. Инверсией в перестановке p называется такая пара позиций i и j, что выполняется

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

Код для проверки

def calc_inversions_simple(array):
    result = 0
    for i, x in enumerate(array):
        for j in range(i + 1, len(array)):
            if array[j] < x:
                result += 1
    return result

def calc_inversions_fast(array):
    tree_size = 1
    while tree_size < len(array):
        tree_size *= 2
    tree_size = tree_size
    tree = [0 for i in range(2 * tree_size)]
    
    def tree_insert(i):
        i += tree_size
        while i > 0:
            tree[i] += 1
            i //= 2
    
    def get_less_count(i):
        if i == tree_size - 1:
            return tree[1]
        i += tree_size
        result = 0
        while i > 0:
            if i % 2 == 0:
                result += tree[i]
            i = (i - 1) // 2
        return result
    
    pos = dict()
    for i, x in enumerate(sorted(array)):
        pos[x] = i
        
    result = 0
    for i in reversed(range(len(array))):
        result += get_less_count(pos[array[i]])
        tree_insert(pos[array[i]])
    return result

def test_insertion_sort_versus_inversiond(array):
    comparisons, swaps = insertion_sort(array)
    print(f"Inversions: {calc_inversions_fast(array)}")
    print(f"Comparisons: {comparisons}")
    print(f"Swaps:       {swaps}")

Итак теорема #2

Для последовательности различных элементов а минимальное количество свопов соседних элементов для установления отсортированного порядка совпадает с количеством инверсий в перестановке p приводящей а в возрастающий порядок

$a_{p_0}<a_{p_1}<\ldots<a_{p_{n-1}}$

Требование на то, что элементы не повторялись упрощают утверждение -- в этом случае сортирующая перестановка единственна. Теперь давайте разбираться: процесс сортировки с использованием свопом можно воспринимать так: мы начинаем с тождественной перестановки 0, 1, 2, ..., n-1, начинаем перестанавливать в ней соседние элементы, в конце должны получить сортирующую перестановку p. У исходной перестановки количество инверсий 0. Если внимательно присмотреться, то одна замена соседних элементов либо увеличивает количество инверсий на 1, либо уменьшает на 1 -- из этого сразу следует, что быстрее чем за количество инверсий точно не получится. Вопрос, получится ли ровно за количество инверсий. Если посмотреть на этот процесс в обратном порядке, т.е. если мы пытаемся с помощью свопов получить из p тождественную перестановку, то выбирая в обратном порядке только такие свопы, которые уменьшают количество инверсий, мы в итоге придем к единственной перестановке с 0 инверсий -- тождественной. Последний винтик в этом пазле -- это то, что у любой перестановки кроме тождественной обязательно должна найтись пара соседних позиций, которая образует инверсию, своп элементов на этой позиции уменьшит количество инверсий.

Наконец возвращаясь от перестановок к сортировкам можно заметить, что свопы элементов, находящихся в неправильном порядке -- это как раз "правильные" свопы. Из теоремы #2 получаем такое интересное следствие

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

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

На КДПВ в частности код GCC отвечающий за алгоритмическое описание std::sort. В GCC, MSVC и Clang используется примерно одна и та же сортировка:

Сначала запускаем quicksort
Если у quicksort слишком много рекурсивных вызовов -- переключаемся на heapsort
Если размер блока маленький -- сортируем вставками

Кажется первые к этому пришли LLVM, потом подхватили остальные, LLVM судя по всему впереди планеты всей, у них там недавно был лютейшая оптимизация -- выжали 2-3% найдя оптимальные сортирующие сети для блоков размера 3 и 5 с помощью AlphaDev.

Если посмотреть на код std::sort в MSVC, то легко увидеть описанную выше логику. А вот в GCC интереснее: сортировка вставками идет отдельно от Introsort, а не внутри неё. Как так? Это такое элегантное использование адаптивности сортировки вставками и особенностями работы quicksort: быстрая сортировка здесь не сортирует блоки меньше 16, а просто игнорирует их. Но по устройству быстрой сортировки несортированные блоки должны остаться на тех же местах, а сортировка вставками за счет своей адаптивности автоматически эти блоки распознаёт. Таким образом в итоге варианты MSVC и GCC делают одно и тоже. Какой из вариантов лучше -- надо замерять. Вроде как с одной стороны GCC делает лишний финальный проход, но с другой стороны за счет того, что мы смотрим на весь массив, а не его отельные кусочки, проще применять векторные оптимизации.

Теорема №3

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

Во-первых, достаточно очевидно, что минимальное число свопов на последовательности из n элементов не должно превосходить n-1, сортировка выбором этой оценки достигает: нашли минимум -- поставили на первое место, среди оставшихся нашли минимум -- поставили на второе место и т.д.

def selection_sort(array):
    comparisons = 0
    swaps = 0
    for i in range(len(array) - 1):
        mini = i
        for j in range(len(array) - i - 1):
            comparisons += 1
            if array[mini] > array[j + i + 1]:
                mini = j + i + 1
            
        if i != mini:
            swaps += 1
            array[mini], array[i] = array[i], array[mini]
    return comparisons, swaps

Но вот все-таки остается вопрос, можно ли меньше? Очевидным образом для отсортированного массива никаких свопов не надо и сортировка выбором ни одного не сделает, а что по поводу частично отсортированных? Сходу непонятно.

Чтобы разобраться нам нужно будет опять обратиться к перестановкам, но прежде чем это сделать расскажу история как теорема №3 появилась. Как-то я давал ровно эту задачу старшеклассникам в качестве упражнения на перестановки. На тот момент у меня было понимание каким образом получить алгоритм с минимальным числом свопов -- он заключался в применении специального алгоритма поверх перестановок, о нем чуть позже. Так вот решение подразумевало написание этого специального алгоритма с перестановками -- он был сложнее для понимания, чем сортировка выбором, но все-таки по силам ученикам. Я был честным преподавателем и не требовал "ровно вот это единственное решение", если бы задачу решили как-то по-другому я был совершенно не против. Сама задача была в олимпиадном формате с достаточно большим количеством случайных тестов, что почти исключало ошибочного решения. И вот случилось то, чего я точно не мог ожидать: все ученики решили эту задачу ... одинаковым способом -- применением сортировки выбором. Скрипя зубами я поставил всем пятёрки и пошел разбираться, провозившись долго над этим я в итоге в эйфорическом настроении пришел к теореме #3

При применении к последовательности из различных элементов сортировка выбором делает минимальное возможное число свопов

Я не уверен, будет ли она всё еще оптимальной при наличии повторов, не проверял и не умею доказывать. Итак, чтобы доказать оптимальность нам понадобится следующий объект

Определение 3. Циклом длины k в перестановке p называется такая последовательность

$i_0, \ldots, i_{k-1}$

такая, что

$p_{i_j}=i_{j+1},~~p_{i_{k-1}}=i_0$

Например в перестановке

Три цикла [1, 5, 0], [3] и [2, 4].

Лемма. Каждый элемент перестановки является частью ровно одного цикла

Доказательство очень простое: берем какую нибудь позицию i и начинаем итерироваться

$i\rightarrow p_i$

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

Так, ну хорошо, а как нам эти циклы помогут? Можно обратить внимание, что у тождественной перестановки из n элементов ровно n циклов и это единственная перестановка с n циклами. Внимательный читатель уже должен догадаться к чему все идет. Более формально теорема №3 выглядит так

Если сортирующая перестановка p для последовательности различных элементов а длины n имеет k циклов, то минимальное число свопов, необходимое для сортировки последовательности -- это n-k и сортировка выбором делает ровно n-k свопов.

Доказательство схоже с теоремой №2, но с использованием циклом вместо инверсий. Любой своп либо увеличивает количество циклов на 1, либо уменьшает на 1. Когда сортировка выбором делает своп, то какой-то из циклов длина l>1 превращается в цикл длины l-1 и цикл длины 1, соответственно количество циклов увеличивается на 1. Детали последнего утверждения предлагаю читателю додумать самостоятельно, но если в конце статьи оставлю ссылку на более подробный англоязычный материал.

Для полноты картины привожу

Код для подсчета количества циклов

def decompose_cycles(permutation):
    n = len(permutation)
    marked = [False for x in permutation]
    cycles = []
    for x in permutation:
        if x < 0 or x >= n:
            return "Not a permutation"

    for i, x in enumerate(permutation):
        if marked[x]:
            continue
        marked[x] = True
        cur = permutation[x]
        cycle = [x]
        while cur != x:
            if marked[cur]:
                return "Not a permutation"
            marked[cur] = True
            cycle.append(cur)
            cur = permutation[cur]
        cycles.append(cycle)
        
    return cycles

def calc_minimum_number_of_swaps(array):
    pos = dict()
    for i, x in enumerate(sorted(array)):
        pos[x] = i
  
    num_cycles = len(decompose_cycles([pos[x] for x in array]))
    return len(array) - num_cycles

def test_selection_sort_versus_cycles(array):
    expected_swaps = calc_minimum_number_of_swaps(array)
    comparisons, swaps = selection_sort(array)
    // expected_swaps should equals swaps

Этот пример для меня впоследствии стал показательным вот в каком контексте. Я часто слышу от людей что-то в духе: "Блин, я вот в университете изучал вот эту хрень и она мне потом в жизни вообще никогда не пригодилась". Вышеописанный случай показывает другой взгляд на ситуацию. Высока вероятность, что несмотря на Вашу нелюбовь к этой хрени, у Вас таки была возможность эту хрень применить, но она прошла у вас прямо под носом, а Вы этого не заметили из-за того, что плохо эту хрень понимали.

Заключение

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

Ну и на последок, пишите надёжные тесты, мотивируйте людей проявлять творческую натуру, а не "нет, я хочу, чтобы Вы решили задачу вот таким методом, а не этим", и тогда возможно и Вас ждут удивительные открытия :) Успехов!

Ссылка на более подробное и более математическое описание вышеизложенного с кодом

https://github.com/Malkovsky/interactive-visualization/blob/master/examples/sorts.ipynb

P. S.

Меня таки тоже покусали блогеры, и я сам таким стал

Реклама своего ТГ

Совсем недавно завел ТГ с целью писать про то, что хорошо умею -- применять на практике сложные алгоритмы/математику.

Frontender`s Spectre

[Ulbi TV] Алгоритмы и структуры данных ФУНДАМЕНТАЛЬНЫЙ КУРС от А до Я

Три теоремы о сортировках