팬케이크 정렬이란?
팬케이크 정렬(Pancake Sort)은 뒤집개로 팬케이크를 뒤집는 모습에서 착안한 정렬 알고리즘입니다. 배열 A가 주어졌을 때 이 기법으로 A를 정렬하는데, 핵심 제약 조건은 rev(arr, i)라는 단 하나의 연산만 사용할 수 있다는 점입니다. 이 연산은 배열 arr의 0번째 인덱스부터 i번째 인덱스까지의 원소들을 한꺼번에 뒤집습니다.
전체적인 아이디어는 선택 정렬(selection sort)과 유사합니다. 즉, 가장 큰 원소를 반복적으로 배열의 끝에 배치하면서 정렬 대상 범위를 하나씩 줄여 나가는 방식입니다. 예를 들어 입력이 [54, 85, 52, 25, 98, 75, 25, 11, 68]이라면, 최종 결과는 [11, 25, 25, 52, 54, 68, 75, 85, 98]이 됩니다.
알고리즘 동작 과정
size를 n으로 초기화합니다.
size가 1보다 큰 동안 다음을 반복합니다.
index := arr[0]부터 arr[size-1] 범위에서 최댓값의 인덱스를 찾습니다.
rev(arr, index)를 호출하여 최댓값을 배열의 맨 앞으로 이동시킵니다.
rev(arr, 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] << " ";
}입력
[54, 85, 52, 25, 98, 75, 25, 11, 68]
출력
[11,25,25,52,54,68,75,85,98]
시간 및 공간 복잡도
팬케이크 정렬의 시간 복잡도는 O(n²)입니다. 매 반복마다 최댓값을 찾는 데 O(n)이 소요되고, 두 번의 뒤집기 연산에도 각각 최대 O(n)만큼 걸리며, 이 과정이 n-1번 반복되기 때문입니다. 반면 추가 배열 없이 제자리(in-place) 정렬이 가능하므로 공간 복잡도는 O(1)입니다.