Ordenamiento de panqueques

1. Algoritmo de ordenamiento de panqueques
2. Ejemplo de ordenamiento de panqueques
3. Implementación del algoritmo ordenamiento de panqueques
4. Complejidad del algoritmo ordenamiento de panqueques

La ordenamiento de panqueques es un algoritmo de ordenación basado en la inversión. Se basa en el problema de la vida real de asemejar panqueques en un plato con la ayuda de una espátula. Recibe su nombre de la operación de volteo utilizada en el algoritmo, análoga a la de voltear panqueques. A diferencia de la mayoría de los algoritmos de ordenación que tratan de minimizar el número de comparaciones requeridas para realizar la ordenación, éste trata de ordenar el array en el mínimo de reversiones. Al igual que ordenamiento por selección, también coloca el elemento máximo al final.

Algoritmo de ordenamiento de panqueques

Supongamos que tenemos un array sin ordenar A[] que contiene n elementos.

PancakeSort()

Flip()

Ejemplo de ordenamiento de panqueques

Supongamos que tenemos el array (3, 5, 2, 1, 7, 6, 4). Vamos a ordenarlo utilizando el algoritmo de ordenamiento de panqueques.

• Primera iteración

mi = 4, curr = 7

• Segunda iteración

mi = 1, curr = 6

• Tercera iteración

mi = 2, curr = 5

• Cuarta iteración

mi = 0, curr = 4

• Quinta iteración

mi = 2, curr = 3

• Sexta iteración

mi = 0, curr = 2

Obtenemos el array ordenado final como 1, 2, 3, 4, 5, 6, 7.

Implementación del algoritmo ordenamiento de panqueques

#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";
}

Complejidad del algoritmo ordenamiento de panqueques

Complejidad temporal

• Caso medio

En promedio, se realizan n-i comparaciones en la i-th pasada de la ordenamiento de panqueques. Por tanto, si hay n iteraciones, la complejidad temporal media puede venir dada por :

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

Por lo tanto, la complejidad temporal es del orden de [Big Theta]: O(n²). También se puede calcular contando el número de bucles. Hay un total de dos bucles de n iteraciones haciendo la complejidad: n*n = n².

• El peor caso

El peor caso se produce cuando los elementos son alternativamente pequeños y grandes. Se requiere un total de 2n-3 volteos. El número de vueltas necesarias es del orden de O(n). La complejidad temporal en el peor de los casos es [Big O] O(n²).

• El mejor caso

El mejor caso se da cuando el array ya está ordenado y no se requiere ningún volteo. La complejidad temporal del mejor caso es [Big Omega]: O(n).

Complejidad espacial

La complejidad espacial de este algoritmo es O(n) porque no se necesita más memoria que una variable temporal.