팬케이크 정렬

1. 팬케이크 정렬 알고리즘
2. 팬케이크 정렬 예
3. 팬케이크 정렬 알고리즘 구현
4. 팬케이크 정렬 알고리즘 복잡성

팬케이크 정렬은 반전 기반 정렬 알고리즘입니다. 그것은 주걱을 사용하여 접시에 팬케이크를 닮은 실제 문제를 기반으로합니다. 팬케이크 뒤집기와 유사한 알고리즘에서 사용되는 뒤집기 작업에서 이름을 얻습니다. 정렬을 수행하는 데 필요한 비교 수를 최소화하려는 대부분의 정렬 알고리즘과 달리 최소 반전으로 배열을 정렬하려고합니다. 선택 정렬와 마찬가지로 끝에 최대 요소도 배치합니다.

팬케이크 정렬 알고리즘

n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.

PancakeSort()

Flip()

팬케이크 정렬 예

배열이(3, 5, 2, 1, 7, 6, 4)라고 가정합니다. 팬케이크 정렬 알고리즘을 사용하여 정렬합니다.

• 첫 번째 반복

mi = 4,curr = 7

• 두 번째 반복

mi = 1,curr = 6

• 세 번째 반복

mi = 2,curr = 5

• 네 번째 반복

mi = 0,curr = 4

• 다섯 번째 반복

mi = 2,curr = 3

• 여섯 번째 반복

mi = 0,curr = 2

최종 정렬 된 배열을1, 2, 3, 4, 5, 6, 7로 얻습니다.

팬케이크 정렬 알고리즘 구현

#include <bits/stdc++.h>
using namespace std;
void flip(int arr[], int i) {
  int temp, start = 0;
  while (start < i) {
    temp = arr[start];
    arr[start] = arr[i];
    arr[i] = temp;
    start++;
    i--;
  }
}

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

void pancakeSort(int arr[], int n) {
  for (int i = n; i > 1; i--) {
    int mi = findMax(arr, i);
    if (mi != i - 1) {
      flip(arr, mi);
      flip(arr, i - 1);
    }
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  pancakeSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

팬케이크 정렬 알고리즘 복잡성

시간 복잡성

• 평균 사례

평균적으로 팬케이크의 i번째 패스에서 n-i를 비교한다. 따라서 n개의 반복이있는 경우 평균 시간 복잡도는 다음과 같이 지정할 수 있습니다.

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

따라서 시간 복잡도는 [Big Theta] : O(n²) 정도입니다. 루프 수를 세어 계산할 수도 있습니다. 복잡하게 만드는n 반복의 총 2 개의 루프가 있습니다 : n * n = n².

• 최악의 경우

최악의 경우는 요소가 크고 작은 요소를 번갈아 가며 발생합니다. 총 ‘2n-3’번 플립이 필요합니다. 필요한 플립 수는 O(n)순서입니다. 최악의 경우 시간 복잡도는 [Big O] : O(n²)입니다.

• 베스트 케이스

최상의 경우는 배열이 이미 정렬되어 있고 뒤집기가 필요하지 않을 때 발생합니다. 최적의 시간 복잡도는 [Big Omega] :O(n)입니다.

공간 복잡성

이 알고리즘의 공간 복잡도는 임시 변수 이외의 추가 메모리가 필요하지 않기 때문에O(n)입니다.