การจัดเรียงแบบแพนเค้ก (Pancake Sorting) ใน C++

การจัดเรียงแบบแพนเค้ก (Pancake Sorting)

การจัดเรียงแบบแพนเค้กเป็นอัลกอริธึมที่ใช้การดำเนินการเดียวคือ rev(arr, i) ซึ่งกลับลำดับองค์ประกอบของอาร์เรย์จากตำแหน่ง 0 ถึง i แนวคิดคล้าย Selection Sort: วางค่าสูงสุดไว้ท้าย แล้วลดขนาดอาร์เรย์ลงเรื่อยๆ

ตัวอย่าง: อินพุท [54,85,52,25,98,75,25,11,68] ผลลัพธ์ [11,25,25,52,54,68,75,85,98]

ขั้นตอนการแก้ปัญหา

1. size := n
2. ในขณะที่ size > 1:
   • หา index ของค่าสูงสุดในช่วง [0, size-1]
   • rev(arr, index) (นำค่าสูงสุดมาตำแหน่งแรก)
   • rev(arr, size-1) (นำค่าสูงสุดไปตำแหน่งสุดท้ายของช่วงปัจจุบัน)
   • size := size - 1

ตัวอย่างโค้ด 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] << " ";
    return 0;
}

อินพุทและเอาต์พุทตัวอย่าง

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

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