algorithm
पैनकेक सॉर्ट करें

पैनकेक सॉर्ट बेसिक जानकारी

पैनकेक सॉर्ट , आकार के क्रम में पेनकेक्स के एक अव्यवस्थित स्टैक को छांटने की गणितीय समस्या के लिए बोलचाल का शब्द है, जब स्टैक में किसी भी बिंदु पर एक स्पैटुला डाला जा सकता है और इसके ऊपर सभी पेनकेक्स को फ्लिप किया जा सकता है। पैनकेक संख्या किसी दिए गए पैनकेक के लिए आवश्यक न्यूनतम संख्या की फ़्लिप है।

एक पारंपरिक सॉर्टिंग एल्गोरिदम के विपरीत, जो संभवतया सबसे कम तुलना के साथ क्रमबद्ध करने का प्रयास करता है, लक्ष्य अनुक्रम को यथासंभव कुछ उलट क्रम में क्रमबद्ध करना है।

चयन सॉर्ट के समान कुछ करने का विचार है। हम अंत में एक जगह अधिकतम तत्व रखते हैं और वर्तमान सरणी के आकार को एक से कम करते हैं।

समस्या का निराकरण:

1. पैनकेक्स को सबसे छोटे (ऊपर) से सबसे बड़े (सबसे नीचे) तक ऑर्डर करने की आवश्यकता है, शुरुआती स्टैक को किसी भी क्रम में व्यवस्थित किया जा सकता है।
2. मैं केवल पूरे स्टैक को फ्लिप करने का प्रदर्शन कर सकता हूं।
3. स्टैक के निचले भाग में एक विशिष्ट पैनकेक को फ्लिप करने के लिए, हमें पहले इसे शीर्ष पर फ़्लिप करना होगा (फिर इसे फिर से नीचे तक फ़्लिप करना होगा)।
4. प्रत्येक पैनकेक को ऑर्डर करने के लिए ऊपर की तरफ एक फ्लिप की आवश्यकता होगी और एक को अपने अंतिम स्थान पर नीचे फ्लिप करना होगा।

सहज ज्ञान युक्त एल्गोरिथ्म:

1. ऑर्डर पैनकेक का सबसे बड़ा पता लगाएं और इसे नीचे तक फ्लिप करें (आपको इसे पहले स्टैक के शीर्ष पर फ्लिप करने की आवश्यकता हो सकती है)।

2. स्टेप एक तब तक दोहराएं जब तक कि स्टैक ऑर्डर न हो जाए।

3. यही है, एक दो कदम एल्गोरिथ्म काम करेगा।

पैनकेक सॉर्ट एल्गोरिथ्म का उदाहरण:

सहायक स्थान: O(1)
समय जटिलता: O(n^2)

C # कार्यान्वयन

public class PancakeSort
{
    private static void SortPancake(int[] input, int n)
    {
        for (var bottom = n - 1; bottom > 0; bottom--)
        {
            var index = bottom;
            var maxIndex = input[bottom];
            int i;
            for (i = bottom - 1; i >= 0; i--)
            {
                if (input[i] > maxIndex)
                {
                    maxIndex = input[i];
                    index = i;
                }
            }
            if (index == bottom) continue;
            var temp = new int[n];
            var j = 0;
            for (i = bottom; i > index; i--,j++)
            {
                temp[j] = input[i];
            }
            for (i = 0; i < index; i++, j++)
            {
                temp[j] = input[i];
            }
            if (temp.Length > j) temp[j] = input[index];
            for (i = 0; i <= bottom; i++)
            {
                input[i] = temp[i];
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortPancake(input, input.Length);
        return input;
    }
}