C++でのパンケーキの並べ替え

配列Aがあるとすると、Aに対してパンケーキソート手法を実行します。ここでの主な制約は、rev（arr、i）という1つの操作しか使用できないことです。これにより、arrの要素が0からi番目の位置に反転します。このアイデアは、選択ソートのようなものです。 max要素を繰り返し配置して、配列のサイズを小さくします。したがって、入力が[54,85​​,52,25,98,75,25,11,68]の場合、結果は[11,25,25,52,54,68,75,85,98]になります。

これを解決するには、次の手順に従います-

• サイズ：=n

• サイズ>1の場合、実行

  • index：=[0 to size – 1]

    からのarrの最大要素のインデックス

  • rev（arr、index）

  • rev（arr、size-1）

  • サイズ：=サイズ-1

理解を深めるために、次の実装を見てみましょう-

例

#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] << " ";
}

入力

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

出力

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