একটি প্যানকেক বাছাই সমস্যা?

এখানে আমরা প্যানকেক সর্ট নামে আরেকটি সাজানোর সমস্যা দেখব। এই সমস্যা সহজ. আমরা একটি অ্যারে আছে. আমাদের এই সাজাতে হবে। কিন্তু আমরা rev(arr, i) নামে একটি মাত্র অপারেশন ব্যবহার করতে পারি। এটি arr-এর উপাদানগুলিকে 0 থেকে ith অবস্থানে উল্টে দেবে।

এই ধারণা নির্বাচন সাজানোর মত. আমরা বারবার প্রান্তে সর্বোচ্চ উপাদান রাখি এবং অ্যারের আকার হ্রাস করি। আসুন ধারণা পেতে অ্যালগরিদম দেখি।

অ্যালগরিদম

প্যানকেকসর্ট(arr, n)

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