ปัญหาการคัดแยกแพนเค้ก?

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

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

อัลกอริทึม

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

ตัวอย่าง

#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