パンケーキソート

1. パンケーキソートアルゴリズム
2. パンケーキソートの例
3. パンケーキソートアルゴリズムの実装
4. パンケーキソートアルゴリズムの計算複雑性

パンケーキソートは、反転ベースのソートアルゴリズムです。これは、ヘラの助けを借りて皿の上のパンケーキに似ているという現実の問題に基づいています。その名前は、パンケーキを反転させるアルゴリズムで使用されている反転操作に由来しています。ソートの実行に必要な比較の数を最小化しようとする多くのソートアルゴリズムとは異なり、このアルゴリズムは配列を最小の反転でソートしようとします。選択ソートと同様に、最大の要素を最後に配置します。

パンケーキソートアルゴリズム

ここでは、n 要素を含むソートされていない配列 A[] があると仮定してみましょう。

PancakeSort())

Flip() を用いて A[i] の最大要素を正しい位置に移動させる

パンケーキソートの例

配列があるとしましょう。(3, 5, 2, 1, 7, 6, 4). これをパンケーキソートアルゴリズムを用いてソートします。

• 最初の繰り返し

mi = 4, curr = 7

• 2 回目のイテレーション

mi = 1, curr = 6

• 第三反復

mi = 2, curr = 5

• 第四反復

mi = 0, curr = 4

• 第五反復

mi = 2, curr = 3

• 第六反復

mi = 0, curr = 2

最終的にソートされた配列を 1, 2, 3, 4, 5, 6, 7 とします。

パンケーキソートアルゴリズムの実装

#include <bits/stdc++.h>
using namespace std;
void flip(int arr[], int i) {
  int temp, start = 0;
  while (start < i) {
    temp = arr[start];
    arr[start] = arr[i];
    arr[i] = temp;
    start++;
    i--;
  }
}

int findMax(int arr[], int n) {
  int mi = 0;
  for (int i = 0; i < n; ++i)
    if (arr[i] > arr[mi]) mi = i;
  return mi;
}

void pancakeSort(int arr[], int n) {
  for (int i = n; i > 1; i--) {
    int mi = findMax(arr, i);
    if (mi != i - 1) {
      flip(arr, mi);
      flip(arr, i - 1);
    }
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  pancakeSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

パンケーキソートアルゴリズムの計算複雑性

時間計算量

• 平均ケース

平均して, パンケーキソートの ith パスでは n-i の比較が行われる。したがって、n 回の繰り返しがある場合、平均的な時間の複雑さは.

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

したがって、時間の複雑さは [Big Theta]のオーダーになります。O(n²). また、ループの数を数えて計算することもできます。n*n = n²となります。

• 最悪の場合

小要素と大要素が交互に並んでいる場合に最悪のケースが発生します。合計で 2n-3 の反転が必要です。必要なフリップの数は O(n) のオーダーです。最悪の場合の時間的複雑さは [Big O]です。O(n²).

• 最良の場合

ベストケースは、配列が既にソートされていて、反転が不要な場合です。最良の時間的複雑さは[ビッグオメガ]: O(n) です。

空間計算量

テンポラリ変数以外に余分なメモリを必要としないため、このアルゴリズムの空間複雑度は O(n) です。