C++ में पैनकेक छँटाई

मान लीजिए कि हमारे पास एक सरणी ए है, हम ए पर पैनकेक सॉर्ट तकनीक का प्रदर्शन करेंगे। यहां मुख्य बाधा यह है कि हम केवल एक ऑपरेशन का उपयोग कर सकते हैं जिसे रेव (एआर, आई) कहा जाता है। यह गिरफ्तारी के तत्वों को 0 से ith स्थिति में उलट देगा। यह विचार चयन प्रकार की तरह है। हम बार-बार अधिकतम तत्व को अंत में रखते हैं जिससे सरणी का आकार कम हो जाता है। तो अगर इनपुट [54,85,52,25,98,75,25,11,68] जैसा है, तो परिणाम [11,25,25,52,54,68,75,85,98] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• आकार :=n

• जबकि आकार> 1, करें

  • अनुक्रमणिका :=अधिकतम तत्व की अनुक्रमणिका [0 से आकार – 1] तक गिरती है

  • रेव (गिरफ्तारी, अनुक्रमणिका)

  • रेव (गिरफ्तारी, आकार - 1)

  • आकार :=आकार - 1

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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, i;
   for (index = 0, i = 0; i < n; ++i){
      if (arr[i] > arr[index]) {
         index = i;
      }
   }
   return index;
}
int 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] << " ";
}

इनपुट

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

आउटपुट

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