Алгоритм сортировки циклов

Question

Я просматривал Интернет, когда обнаружил, что существует алгоритм, называемый сортировкой циклов, который делает наименьшее количество операций записи в память. Но я нигде не могу найти алгоритм. Как определить, существует ли цикл или не в массиве? Кто-нибудь может дать полное объяснение этого алгоритма?

Answer 1

Алгоритм сортировки циклов мотивируется чем-то, что называется разложение цикла .Разложение циклов лучше всего объяснить на примере.Предположим, у вас есть этот массив:

4 3 0 1 2

Давайте представим, что у нас есть эта последовательность в отсортированном порядке, как показано здесь:

0 1 2 3 4

Как бы мы перетасовали этот отсортированный массивдобраться до перемешанной версии?Хорошо, давайте разместим их рядом:

0 1 2 3 4
4 3 0 1 2

Давайте начнем с самого начала.Обратите внимание, что число 0 поменялось на позицию, изначально удерживаемую 2. Номер 2, в свою очередь, поменялся на позицию, изначально удерживаемую 4. Наконец, 4 поменялся на позицию, изначально удерживаемую 0. Другими словами,все элементы 0, 2 и 4 были повернуты вперед на одну позицию.Это оставляет цифры 1 и 3. Обратите внимание, что 1 переходит туда, где 3, а 3 - туда, где 1.Другими словами, элементы 1 и 3 были зациклены вперед на одну позицию.

В результате вышеприведенных наблюдений мы бы сказали, что последовательность 4 3 0 1 2 имеет циклическое разложение (0 2 4) (1 3).Здесь каждая группа терминов в скобках означает «циклический цикл этих элементов вперед».Это означает цикл 0 до места, где 2, 2 до места, где 4, и 4 до места, где был 0, затем цикл 1 до места, где 3 и 3 до места, где 1.

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

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

Answer 2

Вот реализация Python, если кому-то нужно

def cycleSort(vector):
    writes = 0

    # Loop through the vector to find cycles to rotate.
    for cycleStart, item in enumerate(vector):

        # Find where to put the item.
        pos = cycleStart
        for item2 in vector[cycleStart + 1:]:
            if item2 < item:
                pos += 1

        # If the item is already there, this is not a cycle.
        if pos == cycleStart:
            continue

        # Otherwise, put the item there or right after any duplicates.
        while item == vector[pos]:
            pos += 1
        vector[pos], item = item, vector[pos]
        writes += 1

        # Rotate the rest of the cycle.
        while pos != cycleStart:

            # Find where to put the item.
            pos = cycleStart
            for item2 in vector[cycleStart + 1:]:
                if item2 < item:
                    pos += 1

            # Put the item there or right after any duplicates.
            while item == vector[pos]:
                pos += 1
            vector[pos], item = item, vector[pos]
            writes += 1

    return writes


x = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
w = cycleSort(x) 
print w, x