Сортировка цикла - Cycle sort

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

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

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

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

Алгоритм

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

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

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

Выполнение

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

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

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

def cycle_sort(array) -> int:
    """Sort an array in place and return the number of writes."""
    writes = 0

    # Loop through the array to find cycles to rotate.
    for cycle_start in range(0, len(array) - 1):
        item = array[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

        # 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

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

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

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

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

Внешние ссылки

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