algorithm
Cyclus sorteren

Cyclus Sorteren Basisinformatie

Cyclus sorteren is een sorteeralgoritme dat gebruikmaakt van vergelijkingssortering die theoretisch optimaal is in termen van het totale aantal schrijfbewerkingen naar de oorspronkelijke array, in tegenstelling tot enig ander intern algoritme. Cyclus sorteren is een onstabiel sorteeralgoritme. Het is gebaseerd op het idee van permutatie waarbij permutaties worden verwerkt in cycli, die afzonderlijk roteren en een gesorteerde uitvoer retourneren.

Voorbeeld van cyclus sorteren:

Hulpruimte: O(1)
Tijd Complexiteit: O(n^2)

Pseudocode-implementatie

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

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