ধরুন আমাদের একটি অ্যারে A আছে, আমরা A-তে প্যানকেক সাজানোর কৌশলটি সম্পাদন করব। এখানে প্রধান সীমাবদ্ধতা হল আমরা rev(arr, i) নামক শুধুমাত্র একটি অপারেশন ব্যবহার করতে পারি। এটি arr-এর উপাদানগুলিকে 0 থেকে ith অবস্থানে উল্টে দেবে। এই ধারণা নির্বাচন সাজানোর মত. আমরা বারবার প্রান্তে সর্বোচ্চ উপাদান রাখি এবং অ্যারের আকার হ্রাস করি। সুতরাং ইনপুট যদি [54,85,52,25,98,75,25,11,68] এর মত হয়, তাহলে ফলাফল হবে [11,25,25,52,54,68,75,85,98]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
আকার :=n
-
যখন সাইজ> 1, করবেন
-
index :=[0 থেকে আকার - 1]
এ আরআর-এ সর্বাধিক উপাদানের সূচক -
rev(arr, index)
-
rev(arr, আকার - 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]
