Một vấn đề phân loại bánh kếp?

Ở đây chúng ta sẽ thấy một bài toán sắp xếp khác có tên là Pancake sort. Vấn đề này là đơn giản. Chúng tôi có một mảng. Chúng ta phải sắp xếp điều này. Nhưng chúng ta chỉ có thể sử dụng một thao tác gọi là rev (arr, i). Thao tác này sẽ đảo ngược các phần tử của arr từ 0 đến vị trí thứ i.

Ý tưởng này giống như sự sắp xếp lựa chọn. Chúng tôi liên tục đặt phần tử max ở cuối để giảm kích thước của mảng. Hãy để chúng tôi xem thuật toán để có được ý tưởng.

Thuật toán

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

Ví dụ

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

Đầu ra

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