パンケーキソート

パンケーキソート(Pancake sorting)は、ある数列を大きさ順に並べる際に先頭から何番目かまでをひっくり返す最小の手数を求める問題である. 先頭から途中までを一気にひっくり返さなくてはならないのがポイント. Bill Gatesなどらがその上界を求め効率的なソートを提示している.

最も簡単で効率の悪いパンケーキソートのアルゴリズムを示す. 方針 誰もが思いつくようにソートしなくてはならない数字の中で最大のものが最も下にくるようにひっくり返すことを繰り返す. 以下の画像のようにこの操作は二回で完了することがわかる. そのためこれは多くとも2n-3回の操作で行える.しかし、明らかによりよいアルゴリズムがありそうではある.

詳細はBill Gatesの発表論文を参照してください. Gatesによってひっくり返す手数は(5n+5)/3が上界であることが示されています. ポイントは連続するblockを作成しつつ全体をソートしていくことです.