algorithm
Cykelsortering

Grundläggande information om cykelsortering

Cycle Sort är sorteringsalgoritm som använder jämförelsesorter som teoretiskt sett är optimalt i termer av det totala antalet skrivningar till originalmatris, till skillnad från någon annan sorteringsalgoritm på plats. Cykelsortering är instabil sorteringsalgoritm. Det är baserat på idén om permutation där permutationer tas upp i cykler, som individuellt roterar och returnerar en sorterad utgång.

Exempel på cykelsortering:

Hjälprum: O(1)
Tidskomplexitet: O(n^2)

Pseudocode-implementering

(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 # Implementering

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;
    }
}