algorithm
Cycle Sort

Cycle Sort Grundinformationen

Cycle Sort ist ein Sortieralgorithmus, der die Vergleichssortierung verwendet, die theoretisch im Hinblick auf die Gesamtzahl der Schreibvorgänge in das ursprüngliche Array optimal ist, im Gegensatz zu allen anderen Direktsortieralgorithmen. Die Zyklus-Sortierung ist ein instabiler Sortieralgorithmus. Es basiert auf der Idee der Permutation, bei der Permutationen in Zyklen berücksichtigt werden, die einzeln rotieren und eine sortierte Ausgabe zurückgeben.

Beispiel für Cycle Sort:

Hilfsraum: O(1)
Zeitkomplexität: O(n^2)

Pseudocode-Implementierung

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

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