প্যাঙ্কেক সর্টিং সমস্যা

এখানে আমরা প্যাঙ্কেক সর্ট নামক আরেকটি সর্টিং সমস্যা দেখব। এটি সহজ। একটি অ্যারে আছে। এটিকে সর্ট করতে হবে। কিন্তু শুধু একটি অপারেশন rev(arr, i) ব্যবহার করতে পারব। এটি arr-কে 0 থেকে i-তম পজিশন পর্যন্ত রিভার্স করবে।

এই আইডিয়া সিলেকশন সর্টের মতো। আমরা বারবার ম্যাক্সিমাম এলিমেন্টকে শেষে রাখি এবং অ্যারের আকার কমিয়ে যাই। অ্যালগরিদমটি দেখে ধারণা নেওয়া যাক।

অ্যালগরিদম

pancakeSort(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