एक पैनकेक छँटाई समस्या?

यहां हम पैनकेक सॉर्ट नाम की एक और सॉर्टिंग समस्या देखेंगे। यह समस्या सरल है। हमारे पास एक सरणी है। हमें इसे क्रमबद्ध करना होगा। लेकिन हम केवल एक ऑपरेशन का उपयोग कर सकते हैं जिसे रेव (एआर, आई) कहा जाता है। यह गिरफ्तारी के तत्वों को 0 से ith स्थिति में उलट देगा।

यह विचार चयन प्रकार की तरह है। हम बार-बार अधिकतम तत्व को अंत में रखते हैं जिससे सरणी का आकार कम हो जाता है। आइए विचार प्राप्त करने के लिए एल्गोरिथम देखें।

एल्गोरिदम

पैनकेकसॉर्ट (गिरफ्तारी, एन)

Begin
   size := n
   while size > 1, do
      index := index of max element in arr from [0 to size – 1]
      rev(arr, index)
      rev(arr, size - 1)
      size := size - 1
   done
End

उदाहरण

#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] << " ";
}

आउटपुट

Sorted array: 11 25 25 52 54 68 75 85 98