Bài toán sắp xếp Bánh kếp (Pancake Sort)

Ở đây chúng ta sẽ xem một bài toán sắp xếp khác tên là Sắp xếp Bánh kếp. Bài toán này đơn giản. Chúng ta có một mảng. Chúng ta phải sắp xếp mảng này. Nhưng chúng ta chỉ có thể sử dụng một phép toán gọi là rev(arr, i). Phép này sẽ đảo ngược các phần tử của arr từ vị trí 0 đến vị trí i.

Ý tưởng này giống như sắp xếp chọn (selection sort). Chúng ta liên tục đặt phần tử lớn nhất vào cuối và giảm kích thước mảng. Hãy xem thuật toán để hiểu ý 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] << " ";
}

Kết quả

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