Войти
 Пример циклической сортировки списка случайных чисел. | |
| Класс | Алгоритм сортировки |
|---|---|
| Структура данных | Массив |
| Наихудший случай производительность | Θ (n) |
| Лучший случай производительность | Θ (n) |
| Средняя производительность | Θ (n) |
| наихудший случай сложность пространства | Θ (n) всего, Θ (1) вспомогательный |
Цикл сортировки - это нестабильный алгоритм сортировки, сравнительная сортировка, который теоретически оптимален с точки зрения общего количества операций записи в исходный array, в отличие от любого другого алгоритма сортировки на месте. Он основан на идее, что сортируемая перестановка может быть разложена на циклы, которые можно по отдельности чередовать для получения отсортированного результата.
В отличие от почти любой другой сортировки, элементы никогда не записываются где-либо еще в массиве просто для того, чтобы убрать их с пути действия. Каждое значение либо записывается ноль раз, если оно уже находится в правильном положении, либо записывается один раз в правильное положение. Это соответствует минимальному количеству перезаписей, необходимых для завершения сортировки на месте.
Сведение к минимуму количества операций записи полезно, когда выполнение операций записи в какой-то огромный набор данных очень дорого, например, с EEPROM, например, Flash-память, где каждая запись сокращает срок службы памяти.
К проиллюстрируйте идею циклической сортировки, рассмотрите список с отдельными элементами. Для элемента a мы можем найти индекс, по которому он появится в отсортированном списке, просто подсчитав количество элементов во всем списке, которые меньше, чем a. Теперь
Цикл смещения для списка "bdeac", при смещении первой буквы b в правильную позицию: Повторение этого процесса для каждого элемента сортирует список с одной операцией записи тогда и только тогда, когда элемент еще не находится в правильном положении. Хотя вычисление правильных позиций занимает 
Чтобы создать рабочую реализацию на основе приведенного выше плана, необходимо решить две проблемы:
Следующая реализация Python выполняет циклическую сортировку массива, подсчитывая количество записей в этот массив, которые потребовались для его сортировки.
def cycle_sort (array) ->int: "" "Сортировка массива на месте и возврат количества записей." "" Write = 0 # Цикл по массиву, чтобы найти циклы для вращения. for cycle_start в диапазоне (0, len (array) - 1): item = array [cycle_start] # Найдите, куда поместить элемент. pos = cycle_start для i в диапазоне (cycle_start + 1, len (array)): if array [i] < item: pos += 1 # If the item is already there, this is not a cycle. if pos == cycle_start: continue # Otherwise, put the item there or right after any duplicates. while item == array[pos]: pos += 1 array[pos], item = item, array[pos] writes += 1 # Rotate the rest of the cycle. while pos != cycle_start: # Find where to put the item. pos = cycle_start for i in range(cycle_start + 1, len(array)): if array[i] < item: pos += 1 # Put the item there or right after any duplicates. while item == array[pos]: pos += 1 array[pos], item = item, array[pos] writes += 1 return writes
Когда массив содержит только дубликаты относительно небольшого количества элементов, constant-time идеальная хеш-функция может значительно ускорить поиск, куда поместить элемент, изменив сортировку с Θ (n) времени на Θ (n + k) времени, где k общее количество хешей. В конечном итоге массив отсортирован в порядке хэшей, поэтому очень важно выбрать хеш-функцию, которая дает вам правильный порядок.
Перед сортировкой создайте гистограмму , отсортированную по хешу, подсчитывая количество вхождений каждого хеша в массив. Затем создайте таблицу с совокупной суммой каждой записи в гистограмме. Затем таблица совокупной суммы будет содержать позицию в массиве каждого элемента. Затем правильное место элементов можно найти с помощью хеширования с постоянным временем и поиска в таблице совокупной суммы, а не с помощью линейного поиска.
^«Циклическая сортировка: линейный Метод сортировки », The Computer Journal (1990) 33 (4): 365-367.
