Chương trình C này triển khai Sắp xếp Pancake trên Mảng số nguyên.
Sắp xếp pancake là một biến thể của bài toán sắp xếp trong đó thao tác được phép duy nhất là đảo ngược các phần tử của một số tiền tố của chuỗi.
Phân loại bánh kếp là thuật ngữ thông tục để chỉ vấn đề toán học về việc sắp xếp một chồng bánh kếp lộn xộn theo thứ tự kích thước khi thìa có thể được cắm vào bất kỳ điểm nào trong ngăn xếp và được sử dụng để lật tất cả các bánh kếp ở trên nó. Số bánh kếp là số lần lật tối thiểu cần thiết cho một số lượng bánh kếp nhất định
Input:5,3,2,1,4 Output:1 2 3 4 5
Giải thích
Nó là một biến thể của bài toán sắp xếp trong đó hoạt động được phép duy nhất là đảo ngược các phần tử của một số tiền tố của dãy. Không giống như một thuật toán sắp xếp truyền thống, cố gắng sắp xếp với ít phép so sánh nhất có thể, mục tiêu là sắp xếp chuỗi theo càng ít đảo ngược càng tốt. Một dạng khác của vấn đề liên quan đến bánh kếp bị cháy, trong đó mỗi chiếc bánh kếp có một mặt bị cháy và tất cả các bánh kếp đều phải có mặt bị cháy ở dưới cùng.
Ví dụ
#include <iostream>
using namespace std;
void do_flip(int *, int, int);
int pancake_sort(int *list, unsigned int length) {
if (length < 2)
return 0;
int i, a, max_num_pos, moves;
moves = 0;
for (i = length;i > 1;i--) {
max_num_pos = 0;
for (a = 0;a < i;a++){
if (list[a] > list[max_num_pos])
max_num_pos = a;
}
if (max_num_pos == i - 1)
continue;
if (max_num_pos){
moves++;
do_flip(list, length, max_num_pos + 1);
}
do_flip(list, length, i);
}
return moves;
}
void do_flip(int *list, int length, int num) {
int swap;
int i = 0;
for (i=0;i < --num;i++) {
swap = list[i];
list[i] = list[num];
list[num] = swap;
}
}
int main(int argc, char **argv) {
int arr[]={5,3,2,1,4};
int n=5;
int moves=pancake_sort(arr, n);
for (int i = 0;i < n;i++) {
printf("%d ", arr[i]);
}
printf(" - with a total of %d moves\n", moves);
}