Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में पैनकेक सॉर्टिंग


मान लीजिए हमारे पास एक सरणी A है, जिस पर हम पैनकेक सॉर्ट तकनीक लागू करेंगे। यहाँ मुख्य प्रतिबंध यह है कि हम केवल एक ऑपरेशन rev(arr, i) का उपयोग कर सकते हैं, जो सरणी के तत्वों को इंडेक्स 0 से i तक उलट देता है। यह विचार सिलेक्शन सॉर्ट जैसा है: हम बार-बार अधिकतम तत्व को अंत में रखते हैं और सरणी का आकार घटाते हैं।

उदाहरण: इनपुट [54,85,52,25,98,75,25,11,68] के लिए परिणाम [11,25,25,52,54,68,75,85,98] होगा।

एल्गोरिदम

  1. size := n (सरणी की लंबाई)।
  2. while size > 1:
    • index := 0 से size-1 तक अधिकतम तत्व का इंडेक्स ढूंढें।
    • rev(arr, index) कॉल करें (अधिकतम तत्व को सामने लाएँ)।
    • rev(arr, size-1) कॉल करें (अधिकतम तत्व को सही स्थान पर ले जाएँ)।
    • size := size - 1 (सॉर्टेड भाग को छोड़ें)।

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

#include <iostream>
using namespace std;

void rev(int arr[], int i) {
    int temp, st = 0;
    while (st < i) {
        temp = arr[st];
        arr[st] = arr[i];
        arr[i] = temp;
        st++; i--;
    }
}

int maxIndex(int arr[], int n) {
    int index = 0;
    for (int i = 1; i < n; ++i) {
        if (arr[i] > arr[index]) index = i;
    }
    return index;
}

void pancakeSort(int arr[], int n) {
    for (int size = n; size > 1; size--) {
        int index = maxIndex(arr, size);
        if (index != size - 1) {
            rev(arr, index);
            rev(arr, size - 1);
        }
    }
}

int main() {
    int arr[] = {54, 85, 52, 25, 98, 75, 25, 11, 68};
    int n = sizeof(arr) / sizeof(arr[0]);
    pancakeSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) cout << arr[i] << " ";
    return 0;
}

इनपुट

[54, 85, 52, 25, 98, 75, 25, 11, 68]

आउटपुट

[11,25,25,52,54,68,75,85,98]
  1. C++ में लाइन रिफ्लेक्शन - Y-अक्ष के समानांतर सममित रेखा जांचें C++ में लाइन रिफ्लेक्शन - Y-अक्ष के समानांतर सममित रेखा जांचें

    समस्या विवरण मान लीजिए हमारे पास 2D तल पर n बिंदु हैं, हमें जांचना है कि क्या y-अक्ष के समानांतर कोई रेखा है जो दिए गए बिंदुओं को सममित रूप से प्रतिबिंबित करती है, दूसरे शब्दों में, जांचें कि क्या कोई ऐसी रेखा मौजूद है जो सभी बिंदुओं को दी गई रेखा पर प्रतिबिंबित करने के बाद मूल बिंदुओं का समुच्चय प

  1. - C++ में कोर्स शेड्यूल IV

    मान लीजिए कुल n कोर्स हैं जिन्हें हम ले सकते हैं, कोर्स 0 से n-1 तक लेबल किए गए हैं।कुछ कोर्स के डायरेक्ट प्रीरिक्विज़ाइट हो सकते हैं, उदाहरण के लिए, कोर्स 0 लेने के लिए हमें पहले कोर्स 1 लेना होगा, जिसे एक जोड़ी के रूप में व्यक्त किया जाता है: [1,0]।इसलिए, यदि हमारे पास कोर्स की संख्या n, डायरेक्ट

  1. C++ में डायगोनल ट्रैवर्स II C++ में डायगोनल ट्रैवर्स II

    मान लीजिए हमारे पास nums नामक लिस्ट ऑफ लिस्ट है, हमें nums के सभी एलिमेंट्स को डायगोनल क्रम में दिखाना है।इसलिए, यदि इनपुट हैतो आउटपुट होगा [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:एक ऐरे ret परिभाषित करेंएक 2D ऐरे v परिभाषित करेंi := 0 से शुरू करें,