Прошел вебинар по сортировкам.

Рассмотрели сортировку выбором и пузырьком. В целом они довольно похожи ,но в то время как пузырьковая требует постоянных перестановок ,сортировка выбором сначала найдет наибольший или наименьший элемент и только потом при необходимости переставит его. Однако все равно оба алгоритмы не очень оптимальные ,и работают за O(n^2).

Иногда требуется найти в массиве k наибольших или наименьших элементов. Таким образом можно произвести частичную сортировку ,и стоимость алгоритмов выше снижается до O(n * k) или O(n) ,тк k будет считаться константой.

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

Рассмотрели блочную сортировку (bucket sort) ,которая предполагает разделение данных на блоки ,например на интервалы. Каждый блок можно быстро отсортировать отдельно. Но слишком много накладных расходов ,тк под каждый блок выделяется доп память. В целом может подойти ,если требуется сортировка в определенном диапазоне. Может быть применена в задаче нахождения топ k элементов.

Поразрядная сортировка (radix sort) предполагает группировку по разрядам поочередно - от меньшего к бОльшему. Суть в том ,что на каждой итерации мы расставляем числа по индексам от 0 до 9. Сначала мы это делаем для разряда единиц ,потом для десятков ,затем сотен и т.д. На каждой такой итерации мы достаем числа в той последовательности ,в какой они добавлялись по индексам. И получается частичная сортировка по разряду числа. В конце на самом большом разряде окажется ,что все числа отсортированы.

В целом такая сортировка может работать за O(n * k) ,где k - максимальный разряд числа в массиве. Если он небольшой ,то алгоритм будет достаточно эффективным. Но работает он только с положительными числами (если не наворачивать костыли). Может подойти для задачи про суффиксный массив ,поэтому для алфовитных символов тоже может подойти.

Из сортировок общего назначения вспомнили про сортировку слиянием и быструю сортировку. Слиянием всегда выполняется за O(n log n) независимо от условий ,в то время как в быстрой все зависит от выбора опорного элемента и того ,отсортирован ли уже массив. Однако сортировка слиянием требует доп память O(n) ,в то время как быстрая может не требовать памяти при реализации in-place. Кстати такую реализацию быстрой сортировки я писал для одной из задач на курсе. Как оказалось на практике именно этот вариант и берут из-за преимущества по расходу памяти O(1).

Однако остается минус в виде того - что реализация подразумевает рекурсию. А это память под кадры стека и ограничение глубины.

Рассмотрели пример модификации Quick sort с 2 опорными элементами ,которая работает эффективнее.

Далее рассмотрели еще некоторые способы решения задач вида N smallest-biggest. Это алгоритм быстрого выбора (Quick Select) ,который в целом напоминает быструю сортировку ,а также решение через структуру данных - кучу ,где на вершине хранится всегда наименьший элемент ,а потом убирается. В случае с кучей ,где все операции можно сделать за O(log k) ,где k - размер кучи ,сложность алгоритма поиска может достигать O(n) ,где k обычно превращается в константу.

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

В целом вебинар очень полезный.