Cycle Sort

Проблема

На флеш-памяти, EEPROM или в системах, где каждая запись стоит дорого (ограниченный ресурс перезаписи, дорогая операция ввода-вывода), важно не количество сравнений, а количество записей. Большинство сортировок делают O(n log n) или O(n²) записей - нужен алгоритм, который сортирует массив с теоретически минимальным числом записей.

Решение

Для каждой позиции i вычисляется, сколько элементов массива меньше a[i] - это и есть правильная позиция элемента в отсортированном массиве. Если элемент уже на своём месте, он пропускается без записи. Иначе элемент записывается на верную позицию, а элемент, который там был, вытесняется и ищет уже свою правильную позицию - так образуется «цикл» перестановок, который завершается, когда вытесненный элемент возвращается в исходную точку. Каждый элемент внутри цикла записывается ровно один раз - общее число записей равно n минус число уже правильно стоящих элементов, что является теоретическим минимумом.

Как это работает

Возьмём массив [5, 1, 4, 2, 3] (n = 5) - ни один элемент не стоит на своём месте. item = 5, вложенный цикл находит 4 элемента меньше пяти среди [1, 4, 2, 3], значит pos = 4. Запись a[4] = 5 вытесняет тройку - это первая из пяти записей алгоритма.

Вытесненная тройка продолжает цикл: среди [1, 4, 2] (позиции 1-3) меньше трёх - 1 и 2, значит pos = 2. Запись на позицию 2 вытесняет 4. Дальше 4 находит pos = 3 (три элемента: 1, 3, 2 меньше него), вытесняет 2. 2 находит pos = 1, вытесняет 1. Наконец 1 находит pos = 0, замыкая цикл записью на стартовую позицию.

Итог: 5 → позиция 4, 3 → позиция 2, 4 → позиция 3, 2 → позиция 1, 1 → позиция 0 - ровно 5 записей на 5 элементов, ни одной лишней. Массив стал [1, 2, 3, 4, 5] за один проход одного цикла, охватившего все позиции - это и есть теоретический минимум: каждый неправильно стоящий элемент пишется ровно один раз.

Сравним с частично отсортированным входом [3, 1, 2, 4] (n = 4). Цикл, стартующий на позиции 0, охватывает только три элемента: 3 → позиция 2, 2 → позиция 1, 1 → позиция 0 - 3 записи. Позиции 1 и 2 при повторной проверке (cycleStart = 1, 2) оказываются уже верными и пропускаются без единой записи, а позиция 3 (4) вообще не проверяется - алгоритм доходит только до n - 2 включительно.

Для сравнения: сортировка выбором на этом же входе [5, 1, 4, 2, 3] делает до 4 обменов (по одному на позицию, кроме последней), а каждый обмен через временную переменную - это 3 записи, то есть до 12 записей против 5 у циклической сортировки. Разница растёт линейно с n: cycle sort пишет не более n раз, а selection sort - до 3(n - 1) раз.

Цена этой экономии - подсчёт правильной позиции. Для каждого элемента цикла алгоритм пересчитывает, сколько элементов меньше него, проходя оставшуюся часть массива заново - O(n) сравнений на каждую запись, откуда и берётся общая сложность O(n²), даже когда реальных записей требуется мало.

Циклическую сортировку впервые описали в контексте задач с минимизацией числа записей в связи с ранними системами хранения данных, где физическая запись была на порядки дороже чтения; сегодня та же логика применяется к флеш-памяти и EEPROM, ресурс перезаписи которых ограничен десятками-сотнями тысяч циклов на ячейку.

Итог: cycle sort - это не «быстрая» сортировка в привычном смысле, а сортировка с гарантированно минимальным числом записей ценой O(n²) сравнений. Там, где записи дёшевы (обычная RAM), этот обмен невыгоден; там, где записи дороги (флеш-память), он становится единственным разумным выбором среди алгоритмов сравнения.

Нюансы выбора

Вместо selection sort, когда важны именно записи - оба алгоритма делают O(n²) сравнений, но cycle sort пишет до 3 раз реже (n записей против до 3(n-1) у selection sort через временную переменную).

На носителях с ограниченным ресурсом перезаписи - флеш-память, EEPROM, где счётчик циклов записи на ячейку исчерпаем и его превышение выводит ячейку из строя.

Против merge sort/quicksort - когда n велико и данные в обычной RAM - там O(n log n) сравнивающие сортировки почти всегда быстрее по общему времени, потому что запись на современном CPU почти так же дешева, как чтение.

Для задач с числами в диапазоне [1, n] без дубликатов - тот же приём «поставь элемент на позицию, равную его значению» решает задачи поиска пропущенного или дублирующегося числа за O(n) времени и O(1) памяти, даже если финальная сортировка не нужна.

Примеры в коде

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

Задачи вида LeetCode "Find All Duplicates/Missing Number" - приём цикличесской сортировки (placement by value) - стандартное O(n)/O(1) решение, регулярно встречающееся в подборках по темам "массивы" и "сортировка на месте".

Курсы по алгоритмам, посвящённые метрикам сложности за пределами счёта сравнений - cycle sort часто приводится как контрпример к интуиции «меньше операций - всегда быстрее»: он минимизирует записи ценой сравнений, показывая, что модель стоимости имеет значение.

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

Когда применять

• Когда сортировка происходит во флеш-памяти или EEPROM, где важно минимизировать число циклов записи.
• В embedded-системах, где запись в память энергозатратна или физически ограничена по ресурсу.

Примеры из практики

• Прошивки embedded-устройств - сортировка конфигурационных данных прямо во флеш-памяти микроконтроллера с ограниченным числом циклов перезаписи.
• Задача «найти недостающее/дублирующееся число» - циклическая сортировка часто используется как приём для задач с числами в диапазоне [1, n] за O(n) времени и O(1) памяти.