정수 배열의 팬케이크 정렬(Pancake Sort)을 구현하는 C 프로그램

이 글에서는 C 언어로 팬케이크 정렬(Pancake Sort)을 구현하는 방법을 소개합니다. 팬케이크 정렬은 일반적인 비교 기반 정렬과 달리, 수열의 접두사(prefix) 요소들을 뒤집는 연산만 허용되는 변형된 정렬 문제입니다.

팬케이크 정렬이란?

팬케이크 정렬은 크기가 뒤죽박죽인 팬케이크 더미를 크기 순서대로 쌓는 수학적 문제에서 유래한 이름입니다. 이때 주걱(spatula)을 더미의 어느 위치든 삽입할 수 있고, 주걱 위에 있는 모든 팬케이크를 한 번에 뒤집을 수 있다고 가정합니다.

여기서 팬케이크 넘버(pancake number)란 주어진 개수의 팬케이크를 정렬하는 데 필요한 최소 뒤집기 횟수를 의미합니다. 전통적인 정렬 알고리즘이 비교 횟수를 최소화하는 데 초점을 맞춘다면, 팬케이크 정렬의 목표는 가능한 한 적은 뒤집기 횟수로 수열을 정렬하는 것입니다.

또한 이 문제에는 '타 버린 팬케이크(burnt pancake)'라는 변형도 있습니다. 각 팬케이크에 탄 면이 있으며, 정렬 후 모든 팬케이크의 탄 면이 아래를 향하도록 만들어야 하는 조건이 추가됩니다.

실행 결과 예시

입력: 5, 3, 2, 1, 4
출력: 1 2 3 4 5

C 언어 구현 코드

#include <iostream>
using namespace std;
void do_flip(int *, int, int);
int pancake_sort(int *list, unsigned int length) {
    if (length < 2)
        return 0;
    int i, a, max_num_pos, moves;
    moves = 0;
    for (i = length;i > 1;i--) {
        max_num_pos = 0;
        for (a = 0;a < i;a++){
            if (list[a] > list[max_num_pos])
                max_num_pos = a;
        }
        if (max_num_pos == i - 1)
            continue;
        if (max_num_pos){
            moves++;
            do_flip(list, length, max_num_pos + 1);
        }
        do_flip(list, length, i);
    }
    return moves;
}
void do_flip(int *list, int length, int num) {
    int swap;
    int i = 0;
    for (i=0;i < --num;i++) {
        swap = list[i];
        list[i] = list[num];
        list[num] = swap;
    }
}
int main(int argc, char **argv) {
    int arr[]={5,3,2,1,4};
    int n=5;
    int moves=pancake_sort(arr, n);
    for (int i = 0;i < n;i++) {
        printf("%d ", arr[i]);
    }
    printf(" - with a total of %d moves\n", moves);
}

코드 동작 원리

pancake_sort 함수는 배열의 끝부터 시작해 매 단계마다 정렬되지 않은 구간에서 최댓값의 위치를 찾습니다. 최댓값이 이미 제자리에 있다면 건너뛰고, 그렇지 않으면 두 번의 뒤집기를 수행합니다. 먼저 최댓값을 배열의 맨 앞으로 뒤집어 올린 뒤, 다시 현재 정렬 대상 위치까지 한 번에 뒤집어 제자리에 놓는 방식입니다.

do_flip 함수는 지정된 위치까지의 접두사를 실제로 뒤집는 역할을 담당하며, 두 포인터를 활용해 요소들을 서로 교환합니다. 함수는 총 뒤집기 횟수(moves)를 반환하며, main 함수에서는 정렬된 배열과 함께 총 뒤집기 횟수를 출력합니다.