algorithm
팬케이크 정렬

팬케이크 정렬 기본 정보

팬케이크 정렬 (Pancake Sort) 은 주걱의 임의의 지점에 삽입 할 수 있고 그 위에있는 모든 팬케이크를 뒤집을 때 사용할 수있는 크기 순으로 팬케이크의 무질서한 스택을 정렬하는 수학적 문제에 대한 구어체 용어입니다. 팬 케잌 번호는 주어진 팬 케익 수에 필요한 최소 반전 횟수입니다.

가능한 한 적은 수의 비교로 정렬을 시도하는 기존의 정렬 알고리즘과는 달리 가능한 한 적은 역전으로 시퀀스를 정렬하는 것이 목표입니다.

아이디어는 선택 정렬과 비슷한 작업을 수행하는 것입니다. 우리는 최후에 하나씩 최대 요소를 배치하고 현재 배열의 크기를 1 줄입니다.

문제 분석 :

1. 팬케이크를 가장 작은 것 (위)에서 가장 큰 것 (아래) 순서로 주문해야하며, 시작 스택은 순서에 관계없이 정렬 될 수 있습니다.
2. 전체 스택을 뒤집기 만 수행 할 수 있습니다.
3. 특정 팬케이크를 스택의 맨 아래로 넘기려면 먼저 맨 위까지 뒤집어야합니다 (다시 맨 아래로 뒤집습니다).
4. 각 팬케이크를 주문하려면 맨 위까지 한 번 올리고 한 번 뒤집 어서 마지막 위치로 내리십시오.

직관적 인 알고리즘 :

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;
    }
}