โปรแกรม C สำหรับ Pancake Sorting

โปรแกรม C นี้ Implement Pancake Sort บนอาเรย์จำนวนเต็ม

Pancake sorting เป็นรูปแบบหนึ่งของปัญหาการจัดเรียงที่อนุญาตให้ดำเนินการได้อย่างเดียวคือการกลับลำดับองค์ประกอบของ prefix บางส่วนของลำดับ

Pancake sorting เป็นคำเรียกทั่วไปสำหรับปัญหาทางคณิตศาสตร์ของการจัดเรียงกองแพนเค้กที่وضลวกลตามขนาด เมื่อสเปทูลาสามารถแทรกได้ที่จุดใดก็ได้ในกองและใช้พลิกแพนเค้กทั้งหมดที่อยู่ด้านบน หมายเลขแพนเค้กคือจำนวนการพลิกน้อยที่สุดที่จำเป็นสำหรับจำนวนแพนเค้กที่กำหนด

Input:5,3,2,1,4 Output:1 2 3 4 5

คำอธิบาย

เป็นรูปแบบของปัญหาการจัดเรียงที่อนุญาตให้ดำเนินการได้อย่างเดียวคือการกลับลำดับองค์ประกอบของ prefix บางส่วนของลำดับ ไม่เหมือนอัลกอริทึมจัดเรียงแบบดั้งเดิมที่พยายามจัดเรียงด้วยการเปรียบเทียบน้อยที่สุด เป้าหมายคือจัดเรียงลำดับด้วยการกลับลำดับน้อยที่สุด รูปแบบปัญหาแบบแปรผันเกี่ยวกับแพนเค้กไหม้ ซึ่งแต่ละแพนเค้กมีด้านไหม้ และทุกแพนเค้กต้องจบลงด้วยด้านไหม้อยู่ข้างล่าง

ตัวอย่างโค้ด C++

#include 
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);
}