Цикличная сортировка :: Cycle Sort

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

Характеристики алгоритма

НазваниеЦикличная сортировка (Cycle sort)
КлассСортировки выбором
УстойчивостьНет
СравненияДа
Сложность по времениХудшаяO(n2 / 2)
СредняяO(n2 / 2)
ЛучшаяO(n2 / 2)
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

Ссылки

Сортировки выбором

Cycle sort

Реализация на различных ЯП