Резюме

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

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

Вы узнали, как можно найти k-й по величине элемент в массиве за $O(n)$. В этом поможет алгоритм поиска k-й порядковой статистики. В этом алгоритме выбирают опорный элемент и в соответствии с ним разбивают массив на три части, в которых располагают:

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

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

Алгоритм поиска k-й порядковой статистики в среднем работает за линейное время. При этом в худшем случае — за квадратичное.

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

Алгоритм быстрой сортировки похож на алгоритм поиска k-й порядковой статистики. Также выбирается опорный элемент, который разбивает массив на три части. Но в этом случае рекурсивный вызов производится для левого и правого подмассивов, пока не дойдем до базового случая.

Еще один алгоритм сортировки, работающий за $O(n \log n)$ — сортировка слиянием. Во время прямого хода рекурсии массив разбивается на две примерно равные части. Эта процедура повторяется рекурсивно для каждой части, пока не наступит базовый случай. В этом алгоритме в качестве критерия остановки рекурсии можно выбрать массив из одного элемента, либо из большего количества элементов. Важно, что из этого рекурсивного вызова будет возвращён уже упорядоченный массив. Если в базовом случае массив состоит из нескольких элементов, его можно отсортировать любым подходящим способом. Во время обратного хода рекурсии два отсортированных подмассива сливаются в один. После возврата из первого рекурсивного вызова на выходе получается полностью отсортированный входной массив.

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

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

Помимо сортировок сравнением существуют алгоритмы, основанные на свойствах элементов.

Например, сортировка подсчётом. Идея алгоритма в том, что нужно посчитать, сколько раз каждое из возможных значений встречается во входных данных. Для вывода ответа нужно вернуть по порядку элементы от самого меньшего до самого большего с учётом их количества. Алгоритму требуется знать диапазон возможных значений элементов. Также для работы ему нужна дополнительная память для хранения счётчиков, объём которой зависит от диапазона значений элементов. В рассмотренной реализации алгоритм не устойчивый.

Сложность алгоритма при реализации с использованием массива $O(n+k)$, где $k$ — диапазон значений элементов.

Поразрядная сортировка использует идею сортировки подсчётом. В рассмотренном алгоритме сортировка подсчётом по очереди применяется к каждому из разрядов, начиная с последнего. После сортировки по первому разряду данные становятся упорядочены. Для реализации нужно знать два параметра: $k$ и $m$, где $k$ — количество разрядов в самом длинном ключе, а $m$ — количество возможных значений разряда ключа.

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

С одним из таких алгоритмов вы познакомились в этом спринте. В этот алгоритме используется сортировка слиянием. Данные, которые нужно отсортировать, разбиваются на чанки. Каждый из чанков сортируется при помощи внутренней сортировки. Затем отсортированные чанки поэтапно сливаются. Общая сложность алгоритма — $O(n \log n)$. Сложность по количеству временных лент — $O(\log k)$.

Тем временем ребята усвоили алгоритмы сортировки и выбрали подходящие методы для решения задач Кондратия.