Ordenamiento de hot cakes

Definición

Problema de ordenar una pila de elementos de tamaños distintos usando únicamente volteos de la parte superior de la pila.

Intuición

Como no se puede extraer un elemento intermedio, primero se lleva a la cima el mayor elemento pendiente y luego se voltea la región desordenada para colocarlo en su posición definitiva al fondo de esa región.

Formulación

Dada una permutación $A=(a_1,\dots ,a_n)$, se busca transformarla en orden creciente mediante operaciones $F_k$ que invierten los primeros $k$ elementos.

El esquema clásico fija los elementos desde el fondo:

para m = n, n-1, ..., 2:
    lleva el máximo de A[1..m] a la cima
    voltea A[1..m] para colocarlo en la posición m

Ejemplo mínimo

La pila $[2,3,1]$ se transforma en $[1,2,3]$ llevando primero el $3$ a la cima y después al fondo:

$$[2,3,1]\stackrel{F_2}{\to }[3,2,1]\stackrel{F_3}{\to }[1,2,3].$$

Contraejemplo o límites

Si se permiten intercambios arbitrarios, ya no se trata de este problema. Además, que un hot cake coincida accidentalmente con su índice objetivo no significa que pertenezca al bloque fijado: el algoritmo necesita conservar un sufijo ordenado.

Relaciones

• Utiliza: Volteo de prefijo.
• Se demuestra con: Invariante de ciclo.
• Se evalúa mediante: Análisis de mejor y peor caso y Complejidad temporal.
• Requiere justificar: Terminación y validez.

Procedencia

• Clase: Algoritmo de los hot cakes
• Fuente: El Algoritmo de los Hot Cakes.
• Página o sección: diapositivas 2–5.

Preguntas abiertas

• ¿Qué entradas fuerzan el mayor número de volteos para esta variante concreta?
• ¿Cómo cambia el algoritmo si la pila debe ordenarse en sentido opuesto?