algorithm
साइकिल क्रमबद्ध करें

साइकिल क्रमबद्ध बुनियादी जानकारी

साइकल सॉर्टिंग एल्गोरिथ्म सॉर्टिंग है जो तुलनात्मक सॉर्ट का उपयोग करता है जो कि किसी भी अन्य जगह-सॉर्टिंग एल्गोरिदम के विपरीत, मूल सरणी को लिखने की कुल संख्या के संदर्भ में सैद्धांतिक रूप से इष्टतम है। साइकिल सॉर्ट अस्थिर छँटाई एल्गोरिथ्म है। यह क्रमपरिवर्तन के विचार पर आधारित है जिसमें क्रमपरिवर्तन को चक्रों में विभाजित किया जाता है, जो व्यक्तिगत रूप से घूमते हैं और एक हल किए गए आउटपुट को वापस करते हैं।

साइकिल सॉर्ट का उदाहरण:

सहायक स्थान: 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;
    }
}