Структуры и алгоритмы данных Python: сортировка списка элементов с использованием Cycle sort

Поиск и сортировка Python: упражнение 16 с решением

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

Пример решения :

Код Python:

# License: https://bit.ly/2V5W81t 
def cycleSort(vector):
    "Sort a vector in place and return the number of writes."
    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
 
 
if __name__ =='__main__':
    x = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
    xcopy = x[::]
    writes = cycleSort(xcopy)
    if xcopy != sorted(x):
        print('Wrong order!')
    else:
        print('%r\nIs correctly sorted using cycleSort to'
              '\n%r\nUsing %i writes.' % (x, xcopy, writes))

Пример вывода:

 [0, 1, 2, 2, 2, 2, 1, 9, 3,5, 5, 8, 4, 7, 0, 6]
Правильно отсортировано с помощью cycleSort для
[0, 0, 1, 1, 2, 2, 2, 2, 3,5, 4, 5, 6, 7, 8, 9]
Используя 10 пишет.

Блок - схема:

Редактор кода Python:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите программу на Python для сортировки списка элементов с использованием Comb sort.
Далее: Напишите программу на Python для сортировки списка элементов, используя сортировку Heap.