A pancake ordering question?

Here we will see another sorting problem called pancake sorting. The question is simple. We have an array. We have to sort this. But we can only use one operation called rev(arr, i). This will flip the element of arr from 0 to the ith position.

The idea is like selection sort. We repeatedly put the largest element at the end to reduce the size of the array. Let's look at the algorithm to understand this idea.

Algorithm

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

Example

#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] << " ";
}

Output

Sorted array: 11 25 25 52 54 68 75 85 98

The above is the detailed content of A pancake ordering question?. For more information, please follow other related articles on the PHP Chinese website!