- @ThothChildren
- 2018.10.21
- PV 483
パンケーキソート
ー 概要 ー
パンケーキソート(Pancake sorting)は、ある数列を大きさ順に並べる際に先頭から何番目かまでをひっくり返す最小の手数を求める問題である.Bill Gatesなどらがその上界を求め効率的なソートを提示している.
この章を学ぶ前に必要な知識
条件
- 大きさの大小がある数列
効果
- 少ない手数で先頭から何番目かまでをひっくり返して効率的にソートする
ポイント
- 時間をかければソートできることは明らかであるが、どう効率的に行うかがポイント
解 説
パンケーキソートのアルゴリズム動画 | |
パンケーキソート(Pancake sorting)は、ある数列を大きさ順に並べる際に先頭から何番目かまでをひっくり返す最小の手数を求める問題である.
先頭から途中までを一気にひっくり返さなくてはならないのがポイント.
Bill Gatesなどらがその上界を求め効率的なソートを提示している. | パンケーキソートとは |
1.効率のよくないパンケーキソート | |
最も簡単で効率の悪いパンケーキソートのアルゴリズムを示す.
方針
誰もが思いつくようにソートしなくてはならない数字の中で最大のものが最も下にくるようにひっくり返すことを繰り返す.
以下の画像のようにこの操作は二回で完了することがわかる.
そのためこれは多くとも2n-3回の操作で行える.しかし、明らかによりよいアルゴリズムがありそうではある. | 最も簡単で効率の悪いパンケーキソートのアルゴリズム |
単純なパンケーキソートで
任意の段階で最大のものを候補の最も下に持ってくる操作.
必ず2回の操作で持ってこれる | |
2.改良されているパンケーキソート | |
詳細はBill Gatesの発表論文を参照してください.
Gatesによってひっくり返す手数は(5n+5)/3が上界であることが示されています.
ポイントは連続するblockを作成しつつ全体をソートしていくことです. | 外部リンク Bill Gatesの発表論文 |
この章を学んで新たに学べる
Comments