Циклическая сортировка

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) В статье содержится список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты .Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июль 2017 )( Узнайте, как и когда удалить это сообщение ) Для проверки данной статьи необходимы дополнительные цитаты . Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Cycle sort" – news · newspapers · books · scholar · JSTOR (July 2017) (Learn how and when to remove this message) (Learn how and when to remove this message)

Циклическая сортировка

Пример циклической сортировки списка случайных чисел.
Сорт	Алгоритм сортировки
Структура данных	Множество
Худший вариант производительности	Θ ( n2 )
Лучшая производительность	Θ ( n2 )
Средняя производительность	Θ ( n2 )
Наихудшая сложность пространства	Θ( n ) общее, Θ( 1 ) вспомогательное
Оптимальный	Нет

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

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

Минимизация количества операций записи полезна, когда запись в какой-то большой набор данных обходится очень дорого, например, в случае с EEPROM, например, флэш-памятью , где каждая запись сокращает срок службы памяти . ^{[ необходима ссылка ]}

Чтобы проиллюстрировать идею циклической сортировки, рассмотрим список с различными элементами. При наличии элемента мы можем найти индекс, под которым он будет встречаться в отсортированном списке , просто подсчитав количество элементов во всем списке, которые меньше . Теперь${\displaystyle x}$${\displaystyle x}$

1. Если элемент уже находится в правильном положении, ничего не делайте.
2. Если это не так, мы запишем его в предполагаемую позицию. Эта позиция занята другим элементом , который мы затем должны переместить в его правильную позицию. Этот процесс перемещения элементов в их правильные позиции продолжается до тех пор, пока элемент не будет перемещен в исходную позицию . Это завершает цикл.${\displaystyle y}$${\displaystyle x}$

Повторение этого процесса для каждого элемента сортирует список, с одной операцией записи, если и только если элемент еще не находится в правильной позиции. В то время как вычисление правильных позиций занимает время для каждого отдельного элемента, что приводит к квадратичному алгоритму времени, количество операций записи сводится к минимуму.${\displaystyle O(n)}$

Чтобы создать рабочую реализацию на основе вышеизложенной схемы, необходимо решить два вопроса:

1. При вычислении правильных позиций мы должны убедиться, что первый элемент цикла не учтен дважды.
2. Если присутствуют дублирующие элементы, то при попытке переместить элемент в правильное положение эта позиция может быть уже занята . Простая перестановка их приведет к бесконечному циклу алгоритма. Вместо этого нам придется вставить элемент после любого из его дубликатов .${\displaystyle x}$${\displaystyle x}$

Следующая реализация Python ^{[1] [ циклическая ссылка ]} выполняет циклическую сортировку массива, подсчитывая количество операций записи в этот массив, которые потребовались для его сортировки.

Питон

def  cycle_sort ( массив )  ->  int : """Сортирует массив на месте и возвращает количество записей.""" пишет  =  0 # Проходим по массиву, чтобы найти циклы для вращения. # Обратите внимание, что последний элемент уже будет отсортирован после первых n-1 циклов. для  cycle_start  в  диапазоне ( 0 ,  len ( массив )  -  1 ): элемент  =  массив [ cycle_start ] # Найдите, куда положить предмет. поз  =  цикл_начало для  i  в  диапазоне ( cycle_start  +  1 ,  len ( array )): если  массив [ i ]  <  элемент : поз  +=  1 # Если элемент уже есть, то это не цикл. если  pos  ==  cycle_start : продолжать # В противном случае поместите элемент туда же или сразу после любых дубликатов. пока  элемент  ==  массив [ поз ]: поз  +=  1 массив [ поз ],  элемент  =  элемент ,  массив [ поз ] пишет  +=  1 # Поверните оставшуюся часть цикла. пока  pos  !=  cycle_start : # Найдите, куда положить предмет. поз  =  цикл_начало для  i  в  диапазоне ( cycle_start  +  1 ,  len ( array )): если  массив [ i ]  <  элемент : поз  +=  1 # Поместите элемент туда или сразу после любых дубликатов. пока  элемент  ==  массив [ поз ]: поз  +=  1 массив [ поз ],  элемент  =  элемент ,  массив [ поз ] пишет  +=  1 вернуться  пишет

Следующая реализация, написанная на C++, просто выполняет циклическую сортировку массива.

шаблон < имя_типа type_array >  void cycle_sort ( type_array * Array , int array_size )    {для ( int cycle_start = 0 ; cycle_start < array_size - 1 ; cycle_start ++ )          {type_array item = Массив [ cycle_start ];   int pos = cycle_start ;   для ( int i = cycle_start + 1 ; i < array_size ; i ++ )          если ( Массив [ i ] < элемент )   поз += 1 ;  если ( pos == cycle_start )   продолжать ;пока ( элемент == Массив [ поз ])   поз += 1 ;  std :: swap ( Массив [ поз ], элемент ); пока ( поз != cycle_start )   {pos = начало_цикла ;  для ( int i = cycle_start + 1 ; i < array_size ; i ++ )          если ( Массив [ i ] < элемент )   поз += 1 ;  пока ( элемент == Массив [ поз ])   поз += 1 ;  std :: swap ( Массив [ поз ], элемент ); }}}

Когда массив содержит только дубликаты относительно небольшого количества элементов, идеальная хэш-функция с постоянным временем может значительно ускорить поиск места для размещения элемента ¹ , превращая сортировку из Θ( n ² ) времени во время Θ( n + k ), где k — общее количество хэшей. Массив оказывается отсортированным в порядке хэшей, поэтому важно выбрать хэш-функцию, которая даст вам правильный порядок.

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

^ «Циклическая сортировка: метод линейной сортировки», The Computer Journal (1990) 33 (4): 365-367.

• Первоисточник неограниченного варианта
• Cyclesort — любопытный алгоритм сортировки