algorithm
Цикл сортировки

Цикл сортировки Основная информация

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

Пример сортировки цикла:

Вспомогательное пространство: O(1)
Сложность времени: O(n^2)

Реализация псевдокода

(input)
output = 0
for cycleStart from 0 to length(array) - 2
    item = array[cycleStart]
    pos = cycleStart
    for i from cycleStart + 1 to length(array) - 1
        if array[i] < item:
            pos += 1
    if pos == cycleStart:
        continue
    while item == array[pos]:
        pos += 1
    array[pos], item = item, array[pos]
    writes += 1
    while pos != cycleStart:
        pos = cycleStart
        for i from cycleStart + 1 to length(array) - 1
            if array[i] < item:
                pos += 1
        while item == array[pos]:
            pos += 1
        array[pos], item = item, array[pos]
        writes += 1
return outout

Реализация C #

public class CycleSort
{
    public static void SortCycle(int[] input)
    {
        for (var i = 0; i < input.Length; i++)
        {
            var item = input[i];
            var position = i;
            do
            {
                var k = input.Where((t, j) => position != j && t < item).Count();
                if (position == k) continue;
                while (position != k && item == input[k])
                {
                    k++;
                }
                var temp = input[k];
                input[k] = item;
                item = temp;
                position = k;
            } while (position != i);
        }
    }

    public static int[] Main(int[] input)
    {
        SortCycle(input);
        return input;
    }
}