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

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

แนวคิดคล้าย Selection Sort เราวางสมาชิกสูงสุดไว้ท้ายลดขนาดอาร์เรย์ทีละนิด มาดูอัลกอริทึม

อัลกอริทึม

pancakeSort(arr, n)

Begin
    size := n
    while size > 1, do
        index := index of max element in arr from [0 to size - 1]
        rev(arr, index)
        rev(arr, size - 1)
        size := size - 1
    done
End

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

ผลลัพธ์

Sorted array: 11 25 25 52 54 68 75 85 98