정의

팬케이크 정렬은 배열의 맨 앞에서부터 임의의 길이만큼 통째로 뒤집는 연산(prefix flip)만 사용해서 정렬하는 알고리즘입니다. 매 단계마다 아직 정렬되지 않은 구간의 최댓값을 두 번의 뒤집기로 구간의 맨 끝(제 위치)에 보냅니다.

핵심 특성

• ✓뒤집기는 항상 맨 앞(index 0)부터 시작 - 임의의 두 원소를 직접 교환할 수 없는 제약
• ✓한 라운드 = 두 번의 뒤집기 (최댓값을 맨 앞으로 → 다시 미정렬 구간 맨 끝으로)
• ✓선택 정렬과 비슷하게 매 라운드 최댓값을 확정하지만, 직접 교환 대신 prefix 뒤집기만 사용
• ✓비교는 O(n²), 뒤집기 횟수는 최대 2(n-1)번 - 뒤집기 비용이 핵심인 환경의 사고 훈련용

시간 복잡도