algorithm
Tipo de ciclo

Ciclo de Información Básica

Cycle Sort es un algoritmo de clasificación que utiliza una clasificación de comparación que es teóricamente óptima en términos del número total de escrituras en la matriz original, a diferencia de cualquier otro algoritmo de clasificación en el lugar. La clasificación del ciclo es un algoritmo de clasificación inestable. Se basa en la idea de permutación en la que las permutaciones se dividen en ciclos, que rotan individualmente y devuelven una salida ordenada.

Ejemplo de clasificación del ciclo:

Espacio auxiliar: O(1)
Complejidad del tiempo: O(n^2)

Implementación de pseudocódigo

(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

Implementación de 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;
    }
}