Циклическое разбиение: алгоритм разбиения до 1,5 раз быстрее

Разбиение последовательности является фундаментальным алгоритмом в программировании, который переупорядочивает числа в последовательности на основе опорного значения. Цель состоит в том, чтобы сначала поместить все числа, меньшие опорного значения, а затем остальные числа. Существуют различные применения разбиения, включая быструю сортировку и поиск среднего значения последовательности. В настоящее время существует два известных алгоритма разбиения: схема Ломуто и схема Хоара. Схема Хоара часто предпочтительнее на практике, потому что она выполняет меньше перестановок внутри массива. Предлагается новая схема разбиения, называемая «циклическим разбиением», которая похожа на схему Хоара, но выполняет на 1,5 раза меньше перестановок. Схема циклического разбиения считается почти оптимальной, поскольку количество назначений значений становится почти равным количеству значений, которые изначально не находятся на своем месте. Схема Хоара пересматривается, и ее временная сложность составляет O(N), независимо от того, где две сканирующие операции встречаются друг с другом. Схема Хоара требует 3L/2 назначений, где L — количество значений, которые не находятся на своих местах. Вводится понятие циклов назначений, которое необходимо для оптимизации схемы разбиения Хоара. Представлены различные случаи перестановок, включая циклический сдвиг влево и обращение последовательности, чтобы показать, что некоторые перестановки требуют больше назначений, чем другие.