पैनकेक सॉर्टिंग समस्या

यहां हम पैनकेक सॉर्ट नामक एक अन्य सॉर्टिंग समस्या देखेंगे। यह समस्या सरल है। हमारे पास एक सरणी है। हमें इसे सॉर्ट करना है। लेकिन हम केवल एक ऑपरेशन 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 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