Giả sử chúng ta có một mảng A, chúng ta sẽ thực hiện kỹ thuật sắp xếp Pancake trên A. Ở đây hạn chế chính là chúng ta chỉ có thể sử dụng một phép toán gọi là rev (arr, i). Điều 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. Vì vậy, nếu đầu vào là [54,85,52,25,98,75,25,11,68], thì kết quả sẽ là [11,25,25,52,54,68,75,85,98]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
kích thước:=n
-
trong khi kích thước> 1, thực hiện
-
index:=chỉ mục của phần tử tối đa trong arr từ [0 đến size - 1]
-
rev (arr, chỉ mục)
-
rev (arr, size - 1)
-
size:=size - 1
-
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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 vào
[54, 85, 52, 25, 98, 75, 25, 11, 68]
Đầu ra
[11,25,25,52,54,68,75,85,98]