C++ প্রোগ্রামে প্যানকেক সোর্টিং (Pancake Sorting)

ভূমিকা

প্যানকেক সোর্টিং হলো একটি সোর্টিং অ্যালগরিদম যেখানে একমাত্র অপারেশন হলো অ্যারের প্রিফিক্স (prefix) রিভার্স (flip) করা। লক্ষ্য হলো কমপ্লেক্সিটি কমাতে নয়, বরং কমপ্লেক্সিটি বড় হলেও কম সংখ্যক ফ্লিপ (flip) দিয়ে সোর্ট করা।

উদাহরণ

ইনপুট: 5 3 2 1 4
আউটপুট: 1 2 3 4 5

C++ প্রোগ্রাম উদাহরণ

#include 
using namespace std;

void flip(int* arr, int n, int k) {
    for (int i = 0; i < k/2; i++)
        swap(arr[i], arr[k-1-i]);
}

int pancakeSort(int* arr, int n) {
    int moves = 0;
    for (int curr = n; curr > 1; curr--) {
        int maxPos = 0;
        for (int i = 1; i < curr; i++)
            if (arr[i] > arr[maxPos]) maxPos = i;
        if (maxPos == curr-1) continue;
        if (maxPos != 0) { flip(arr, n, maxPos+1); moves++; }
        flip(arr, n, curr); moves++;
    }
    return moves;
}

int main() {
    int arr[] = {5,3,2,1,4};
    int n = 5;
    int moves = pancakeSort(arr, n);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << "- Moves: " << moves << endl;
    return 0;
}

আউটপুট

1 2 3 4 5 - Moves: 4