【C言語】パンケーキソート（Pancake Sort）の実装プログラムと仕組みを解説

本記事で紹介するCプログラムは、整数型の配列に対してパンケーキソート（Pancake Sort）を実装したものです。

パンケーキソートとは？

パンケーキソートとは、ソート問題の一種で、「配列の先頭から任意の位置までの要素（プレフィックス）を反転させる」という操作だけが許された特殊なソートです。

この名前は、皿に積まれた大きさがバラバラのパンケーキを並べ替える数学的問題に由来しています。フライ返し（へら）をスタック内の任意の位置に差し込み、その上にあるすべてのパンケーキを一気にひっくり返すことで、サイズ順に並べ替えます。このとき必要となる最小の反転回数は「パンケーキ数」と呼ばれています。

通常のソートアルゴリズムとの違い

一般的なソートアルゴリズムが「比較回数をいかに少なくするか」を目指すのに対し、パンケーキソートでは「できるだけ少ない反転回数」で並べ替えを完了することが目的となります。

さらに、この問題には「焦げたパンケーキ（Burnt Pancakes）」と呼ばれる変種もあります。これは、各パンケーキに焦げた面があり、すべてのパンケーキの焦げた面を下向きにして揃えなければならないという追加条件が課されるものです。

入力と出力の例

Input: 5,3,2,1,4
Output: 1 2 3 4 5

パンケーキソートのCプログラム

以下は、パンケーキソートを実装したサンプルコードです。未整列部分の中から最大値の位置を探し、必要に応じて先頭まで反転させてから、範囲全体を反転することで、後ろの要素から順に確定させていくのが基本的な流れです。

#include <iostream>
using namespace std;
void do_flip(int *, int, int);
int pancake_sort(int *list, unsigned int length) {
    if (length < 2)
        return 0;
    int i, a, max_num_pos, moves;
    moves = 0;
    for (i = length;i > 1;i--) {
        max_num_pos = 0;
        for (a = 0;a < i;a++){
            if (list[a] > list[max_num_pos])
                max_num_pos = a;
        }
        if (max_num_pos == i - 1)
            continue;
        if (max_num_pos){
            moves++;
            do_flip(list, length, max_num_pos + 1);
        }
        do_flip(list, length, i);
    }
    return moves;
}
void do_flip(int *list, int length, int num) {
    int swap;
    int i = 0;
    for (i=0;i < --num;i++) {
        swap = list[i];
        list[i] = list[num];
        list[num] = swap;
    }
}
int main(int argc, char **argv) {
    int arr[]={5,3,2,1,4};
    int n=5;
    int moves=pancake_sort(arr, n);
    for (int i = 0;i < n;i++) {
        printf("%d ", arr[i]);
    }
    printf(" - with a total of %d moves\n", moves);
}

プログラムのポイント

• pancake_sort関数： 未整列範囲から最大値の位置を特定し、すでに正しい位置にあればスキップ、そうでなければ反転操作（flip）を最大2回行って末尾側から要素を確定していきます。
• do_flip関数： 指定された位置までの要素を、両端から順に交換しながら反転させる補助関数です。
• moves変数： 実際に実行された反転操作の回数を記録し、最後にソート結果とともに出力します。

このように、比較ベースの標準的なソートとは異なる発想で配列を並べ替えるパンケーキソートは、アルゴリズムの学習や競技プログラミングの練習題材としても非常に興味深いテーマです。