パンケーキソートとは？アルゴリズムの仕組みとC++実装例をわかりやすく解説

この記事では、「パンケーキソート（Pancake Sort）」と呼ばれるもう一つのソート問題について解説します。この問題は非常にシンプルです。与えられた配列をソートすることが目的ですが、使用できるのは rev(arr, i) という一つの操作だけです。この操作は、配列 arr の先頭（0番目）から i 番目までの要素を反転させるものです。

パンケーキソートの発想は選択ソートに似ています。最大の要素を繰り返し配列の末尾に移動させ、そのたびに扱う配列のサイズを一つずつ減らしていくことで、全体をソートします。それでは、アルゴリズムの流れを見ていきましょう。

アルゴリズム

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

アルゴリズムの手順

処理の流れを整理すると、以下のようになります。

1. 未ソート部分のサイズを n として初期化します。
2. サイズが 1 より大きい間、以下を繰り返します。
   • 先頭から size-1 番目までの範囲で最大要素のインデックスを探します。
   • rev(arr, index) で最大要素を先頭に移動させます。
   • rev(arr, size - 1) で全体を反転し、最大要素を未ソート部分の末尾に配置します。
   • size を 1 減らして、ソート済みの部分を除外します。

なお、最大要素がすでに末尾にある場合は反転操作を省略することで、無駄な処理を避けられます。

C++による実装例

#include<iostream>
using namespace std;

// 配列の先頭から i 番目までを反転する関数
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

計算量について

パンケーキソートでは、各ループで最大要素の探索に O(n)、反転操作にも O(n) の時間がかかります。これを n 回繰り返すため、全体的な時間計算量は O(n²) となります。一方、必要な補助メモリは O(1) で済むため、in-place（追加領域不要）なソートアルゴリズムです。実用面ではクイックソートなどの高速な手法が好まれますが、操作の制約がある場面や教育的な題材として非常に興味深いアルゴリズムといえるでしょう。