Цикличная сортировка :: Cycle Sort
Цикличная сортировка ценна тем, что изменения среди элементов массива происходят только в случаях, когда элемент ставится на своё место. Это важно, если перезапись в массиве обходится слишком дорого и актуально минимальные изменения физической памяти.
Характеристики алгоритма
| Название | Цикличная сортировка (Cycle sort) | |
|---|---|---|
| Класс | Сортировки выбором | |
| Устойчивость | Нет | |
| Сравнения | Да | |
| Сложность по времени | Худшая | O(n2 / 2) |
| Средняя | O(n2 / 2) | |
| Лучшая | O(n2 / 2) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Cycle sort
Реализация на различных ЯП