Циклическая сортировка (Cycle Sort)

Циклическая сортировка (Cycle Sort) — это алгоритм сортировки, который работает по принципу перемещения элементов в их окончательные позиции. Он отличается от других алгоритмов сортировки тем, что он минимизирует количество записей, что делает его особенно полезным в ситуациях, когда количество операций записи является критическим фактором (например, в системах с ограниченными ресурсами).

▎Как работает Cycle Sort:

1. Инициализация: Начинаем с первого элемента массива и предполагаем, что это элемент, который мы будем перемещать в его окончательную позицию.

2. Определение позиции: Находим количество элементов, меньших текущего элемента, чтобы определить его окончательную позицию.

3. Перемещение элементов: Перемещаем текущий элемент на его место, сдвигая все элементы, которые должны быть помещены после него, на одну позицию вправо.

4. Повторение: Повторяем процесс для всех элементов массива.

▎Временная сложность:

• Худший случай: O(n²)

• Средний случай: O(n²)

• Лучший случай: O(n)

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

▎Пространственная сложность:

• O(1)

Cycle Sort работает "на месте", что означает, что он не требует дополнительной памяти для хранения копий массива или других структур данных. Он использует лишь фиксированное количество дополнительных переменных для хранения индексов и временных значений.

▎Устойчивость:

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

Реализация алгоритма на C++:

Реализация алгоритма на Python: