배열 A가 있다고 가정하고 A에 대해 팬케이크 정렬 기술을 수행합니다. 여기서 주요 제약은 rev(arr, i)라는 연산 하나만 사용할 수 있다는 것입니다. 이것은 arr의 요소를 0에서 i번째 위치로 반전시킵니다. 이 아이디어는 선택 정렬과 같습니다. 배열의 크기를 줄인 끝에 max 요소를 반복적으로 배치합니다. 따라서 입력이 [54,85,52,25,98,75,25,11,68]과 같으면 결과는 [11,25,25,52,54,68,75,85,98]이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
크기 :=n
-
크기> 1인 동안 수행
-
index :=[0 ~ 크기 – 1]
에서 arr의 최대 요소 인덱스 -
rev(arr, 인덱스)
-
rev(arr, 크기 - 1)
-
크기 :=크기 - 1
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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]