Цикл сортировки - Cycle sort

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

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

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

Сведение к минимуму количества операций записи полезно, когда выполнение операций записи в большой набор данных очень дорого, например, с EEPROM подобно Флэш-память куда каждая запись сокращает срок службы памяти.

Алгоритм

Чтобы проиллюстрировать идею циклической сортировки, рассмотрим список с отдельными элементами. Учитывая элемент а, мы можем найти индекс, по которому это произойдет в отсортированный список просто подсчитав количество элементов во всем списке, которые меньше, чем а. Сейчас же

  1. Если элемент уже находится в правильном положении, ничего не делайте.
  2. Если это не так, мы запишем его в нужное место. Эта позиция занята другим элементом б, который затем нужно переместить в это правильное положение. Этот процесс перемещения элементов в их правильные положения продолжается до тех пор, пока элемент не будет перемещен в исходное положение а. Это завершает цикл.
Цикл смещения для списка "bdeac" при смещении первой буквы б в правильное положение:

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

Выполнение

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

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

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

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

Оптимизация для конкретной ситуации

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

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

Рекомендации

  1. ^ sr: Ciklično sortiranje # Algoritam

внешняя ссылка

^ «Циклическая сортировка: метод линейной сортировки», Компьютерный журнал (1990) 33 (4): 365-367.