Sắp xếp bánh rán (Pancake Sorting) trong C++

Cho mảng A, thực hiện sắp xếp bánh rán (Pancake sort). Chỉ được dùng một phép toán rev(arr, i) – đảo ngược các phần tử từ vị trí 0 đến i. Ý tưởng giống sắp xếp chọn: lặp lại đưa phần tử lớn nhất về cuối và giảm kích thước mảng. Ví dụ: [54,85,52,25,98,75,25,11,68] → [11,25,25,52,54,68,75,85,98].

Giải thuật

• size := n
• Khi size > 1:
  • index := chỉ số phần tử lớn nhất trong arr[0..size-1]
  • rev(arr, index)
  • rev(arr, size-1)
  • size := size - 1

Ví dụ mã C++

#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 = 0;
    for (int i = 1; i < n; ++i)
        if (arr[i] > arr[index]) index = i;
    return index;
}

void 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 vào

[54, 85, 52, 25, 98, 75, 25, 11, 68]

Đầu ra

[11,25,25,52,54,68,75,85,98]