algorithm
パンケーキソート

パンケーキの基本情報のソート

パンケーキソート （ Pancake Sort）は、不規則なスタックのパンケーキを、順番どおりに並べ替えるという数学的な問題の口語で、その上にすべてのパンケーキを反転させるためにスパチュラを挿入することができます。パンケーキ数は、与えられた数のパンケーキに必要なフリップの最小数です。

できるだけ少ない比較でソートを試みる従来のソーティングアルゴリズムとは異なり、目標は可能な限り少ない逆転でシーケンスをソートすることです。

アイデアは、選択ソートに似た何かをすることです。最後に最大要素を1つずつ配置し、現在の配列のサイズを1つ減らします。

問題を解明する：

1. パンケーキを最小（上）から最大（下）に注文する必要がある場合、開始スタックは任意の順序で配置できます。
2. 私は全体のフリップをフリップすることができますスタック全体。
3. 特定のパンケーキをスタックの一番下にフリップするには、最初にパンケーキを上にフリップする必要があります。
4. 各パンケーキを注文するには、一番上に1つ上にフリップし、もう一人は最終的な場所にフリップする必要があります。

直感的なアルゴリズム：

1. 最大のアウト・オブ・オーダーのパンケーキを見つけ出し、それを一番下にフリップします（最初にスタックの先頭に移動する必要があるかもしれません）。

2. スタックが注文されるまで、ステップ1を繰り返します。

3. それで、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;
    }
}