[C/C++] 팬케이크 정렬 알고리즘

Suppose you are given a stack of n pancakes of different sizes. You want to sort the pancakes so that smaller pancakes are on top of larger pancakes. The only operation you can perform is a flip—insert a spatula under the top k pancakes, for some integer k between 1 and n, and flip them all over. Descrive an algorithm to sort any stack of n pancakes using O(n) flips.

 

<코드>

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <time.h>
using namespace std;


void do_flip(int* pancake, int num)
{
    int swap;
    for (int i = 0; i < --num; i++)
    {
        swap = pancake[i];
        pancake[i] = pancake[num];
        pancake[num] = swap;
    }
}

int pancake_sort(int* pancake, int length)
{
    if (length < 2)
        return 0;

    int max_num_pos, flip;
    flip = 0;

    for (int i = length; i > 1; i--)
    {
        max_num_pos = 0;
        for (int j = 0; j < i; j++)
        {
            if (pancake[j] > pancake[max_num_pos])
                max_num_pos = j;
        }

        if (max_num_pos == i - 1)     
            continue;

        if (max_num_pos != 0)
        {
            flip++;
            do_flip(pancake, max_num_pos + 1);
        }
        flip++;
        do_flip(pancake, i);
    }

    return flip;
}



int main()
{
    
    int pancake[] = {4,2,5,3,1};
    int length = sizeof(pancake) / sizeof(pancake[0]); // 배열 원소 개수;

    printf("처음 : ");

    for (int i = 0; i < length; i++)
        cout << pancake[i] << " ";
    cout << endl;

    int flip = pancake_sort(pancake, length);

    printf("\n정렬 후 : ");

    for (int i = 0; i < length; i++)
        cout << pancake[i] << " ";
    cout << endl;

    printf("\n뒤집은 횟수 : %d\n", flip);
}

 

빌 게이츠가 구현한 팬케이크 정렬

n개의 팬케이크들 중에서 가장 큰 팬케이크를 탐색 후 해당 팬케이크 아래에 뒤집게를 넣어 뒤집는다. 이때 가장 큰 팬케이크가 가장 위에 있게 되므로 맨 위 1번째부터 맨 n번째까지 뒤집은 후 다시 n-1번째까지의 팬케이크들 중에서 가장 큰 팬케이크를 탐색한다. 이러한 방식으로 2번째까지 위의 방법을 반복하고 나면 팬케이크들이 정렬되게 된다. 이러한 방식은 가장 큰 팬케이크를 탐색 후 최상단으로 올린 후 다시 자리에 맞게 뒤집는 과정으로 총 2회씩 시간이 소모되므로 시간 복잡도는O(n)이며 최악의 경우 2n-3번의 뒤집기가 필요하다.

최악의 경우는(n번째가 가장 하단)
n번째에 가장 큰 수를 놓기 위해 2회 뒤집기 (총 2회)
n-1번째에 그 다음 큰 수를 놓기 위해 2회 뒤집기 (총 4회)
...
n-k번째에 그 다음 큰 수를 놓기 위해 2회 뒤집기 (총 2k+2회)
...
4번째에 그 다음 큰 수를 놓기 위해 2회 뒤집기 (총 2n-6회)
3번째에 그 다음 큰 수를 놓기 위해 2회 뒤집기 (총 2n-4회)
3번째까지 정렬되었고 1,2번째를 정렬하는 경우 무조건 뒤집는다고 하면

최악의 경우의 수는 2n-4 + 1 = 2n-3

 

 

1. 팬케이크가 4,2,5,3,1(4가 맨 위)인 상황에서 5가 가장 크므로 5의 바로 밑에 뒤집게를 넣고 뒤집는다. 그리고 가장 큰 수인 5가 맨 위에 왔으므로 전체를 뒤집는다.

2. 맨 아래에 가장 큰 팬케이크를 놓았으니 그다음으로 큰 팬케이크인 4 밑에 뒤집게를 넣어 뒤집는다. 그리고 맨 위에 가장 큰 팬케이크(맨 아래는 이미 정렬됐으므로 5는 고려 xx) 4가 있으므로 4,3,1,2 전체를 뒤집는다.

3. 그다음으로 큰 팬케이크인 3이 이미 정렬됐으므로 다음으로 큰 팬케이크인 2를 탐색하는데 맨 위에 있으므로
2,1 전체를 뒤집는다.