팬케이크 정렬(Pancake Sort): 뒤집기 연산 하나로 배열 정렬하기

이번 글에서는 '팬케이크 정렬(Pancake Sort)'이라는 독특한 정렬 문제를 살펴보겠습니다. 이름처럼 팬 위에서 팬케이크를 뒤집는 모습에서 착안한 알고리즘으로, 문제 자체는 매우 단순합니다.

팬케이크 정렬이란?

정렬해야 할 배열이 하나 주어지지만, 사용할 수 있는 연산은 오직 rev(arr, i) 하나뿐입니다. 이 연산은 배열의 첫 번째 요소(인덱스 0)부터 i번째 위치까지의 요소들을 뒤집는 역할을 합니다. 즉, 일반적인 스왑(swap)이나 다른 정렬 기법 없이 '앞부분 뒤집기'만으로 전체 배열을 오름차순으로 정렬해야 하는 것입니다.

팬케이크 정렬의 아이디어는 선택 정렬(Selection Sort)과 유사합니다. 반복적으로 최댓값을 찾아 배열의 끝에 배치하고, 그때마다 정렬 대상 범위를 하나씩 줄여 나가는 방식입니다.

알고리즘 동작 원리

pancakeSort(arr, n)

Begin
    size := n
    while size > 1, do
        index := arr[0..size-1] 범위에서 최댓값의 인덱스
        rev(arr, index)
        rev(arr, size - 1)
        size := size - 1
    done
End

동작 과정을 단계별로 정리하면 다음과 같습니다.

1. 현재 정렬되지 않은 구간에서 최댓값의 위치(index)를 찾습니다.
2. rev(arr, index)를 호출해 최댓값을 배열 맨 앞으로 이동시킵니다.
3. rev(arr, size-1)을 호출해 맨 앞의 최댓값을 정렬되지 않은 구간의 마지막 위치로 보냅니다.
4. 정렬된 부분을 제외하고 size를 1 줄인 뒤, 위 과정을 size가 1이 될 때까지 반복합니다.

최댓값이 이미 올바른 위치에 있다면 불필요한 뒤집기를 생략하면 되므로, 실제 구현에서는 이 경우를 확인하는 조건문을 추가하는 것이 효율적입니다.

C++ 구현 예제

#include<iostream>
using namespace std;

void rev(int arr[], int i) {
    int temp, st = 0;
    while (st < i) {
        temp = arr[st];
        arr[st] = arr[i];
        arr[i] = temp;
        st++;
        i--;
    }
}

int maxIndex(int arr[], int n) {
    int index, i;
    for (index = 0, i = 0; i < n; ++i){
        if (arr[i] > arr[index]) {
            index = i;
        }
    }
    return index;
}

int pancakeSort(int arr[], int n) {
    for (int size = n; size > 1; size--) {
        int index = maxIndex(arr, size);
        if (index != size-1) {
            rev(arr, index);
            rev(arr, size-1);
        }
    }
}

int main() {
    int arr[] = {54, 85, 52, 25, 98, 75, 25, 11, 68};
    int n = sizeof(arr)/sizeof(arr[0]);
    pancakeSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
}

실행 결과

Sorted array: 11 25 25 52 54 68 75 85 98

시간 복잡도

팬케이크 정렬의 시간 복잡도를 분석해 보겠습니다. 크기 n인 배열에 대해 총 n-1회의 순회가 발생하고, 각 순회마다 최댓값 탐색(O(n))과 두 번의 뒤집기 연산(O(n))이 수행됩니다. 따라서 전체 시간 복잡도는 O(n²)입니다. 다만 비교 횟수를 줄이기 위해 최댓값 탐색을 한 번의 뒤집기와 결합하는 등의 최적화 기법도 존재합니다.

팬케이크 정렬은 실무에서 자주 사용되지는 않지만, 제한된 연산만으로 문제를 해결하는 사고방식을 훈련하기에 좋은 알고리즘이며, 코딩 인터뷰나 알고리즘 학습에서 자주 등장하는 주제입니다.