algorithm
パンケーキソート
サーチ…
パンケーキの基本情報のソート
パンケーキソート ( Pancake Sort)は、不規則なスタックのパンケーキを、順番どおりに並べ替えるという数学的な問題の口語で、その上にすべてのパンケーキを反転させるためにスパチュラを挿入することができます。パンケーキ数は、与えられた数のパンケーキに必要なフリップの最小数です。
できるだけ少ない比較でソートを試みる従来のソーティングアルゴリズムとは異なり、目標は可能な限り少ない逆転でシーケンスをソートすることです。
アイデアは、選択ソートに似た何かをすることです。最後に最大要素を1つずつ配置し、現在の配列のサイズを1つ減らします。
問題を解明する:
- パンケーキを最小(上)から最大(下)に注文する必要がある場合、開始スタックは任意の順序で配置できます。
- 私は全体のフリップをフリップすることができますスタック全体。
- 特定のパンケーキをスタックの一番下にフリップするには、最初にパンケーキを上にフリップする必要があります。
- 各パンケーキを注文するには、一番上に1つ上にフリップし、もう一人は最終的な場所にフリップする必要があります。
直感的なアルゴリズム:
最大のアウト・オブ・オーダーのパンケーキを見つけ出し、それを一番下にフリップします(最初にスタックの先頭に移動する必要があるかもしれません)。
スタックが注文されるまで、ステップ1を繰り返します。
それで、2つのステップのアルゴリズムが動作します。
パンケーキソートアルゴリズムの例:
補助空間: O(1)
時間複雑度: O(n^2)
C#の実装
public class PancakeSort
{
private static void SortPancake(int[] input, int n)
{
for (var bottom = n - 1; bottom > 0; bottom--)
{
var index = bottom;
var maxIndex = input[bottom];
int i;
for (i = bottom - 1; i >= 0; i--)
{
if (input[i] > maxIndex)
{
maxIndex = input[i];
index = i;
}
}
if (index == bottom) continue;
var temp = new int[n];
var j = 0;
for (i = bottom; i > index; i--,j++)
{
temp[j] = input[i];
}
for (i = 0; i < index; i++, j++)
{
temp[j] = input[i];
}
if (temp.Length > j) temp[j] = input[index];
for (i = 0; i <= bottom; i++)
{
input[i] = temp[i];
}
}
}
public static int[] Main(int[] input)
{
SortPancake(input, input.Length);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow