প্যানকেক সর্টিং C++-এ

ধরা যাক একটি অ্যারে A আছে, আমরা এর ওপর প্যানকেক সোর্ট টেকনিক প্রয়োগ করব। এখানে প্রধান বাধা হলো আমরা শুধুমাত্র একটি অপারেশন ব্যবহার করতে পারি যা rev(arr, i)। এটি arr-এর 0 থেকে i-তম পজিশন পর্যন্ত উপাদানগুলো রিভার্স করবে। এই ধারণা সিলেকশন সর্টের মতো। আমরা বারবার সর্বোচ্চ উপাদানকে শেষে রেখে অ্যারের আকার কমিয়ে যাব। যদি ইনপুট হয় [54,85,52,25,98,75,25,11,68], তবে ফলাফল হবে [11,25,25,52,54,68,75,85,98]

এটি সমাধান করার ধাপগুলো −

• size := n

• যখন size > 1, তখন করব

  • index := arr-এ 0 থেকে size-1 পর্যন্ত সর্বোচ্চ উপাদানের ইনডেক্স

  • rev(arr, index)

  • rev(arr, size - 1)

  • size := size - 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]