Clasificación de panqueques

Clasificación de panqueques (del inglés  pancake sorting ): algoritmo de clasificación . La única operación permitida en el algoritmo es invertir los elementos de la secuencia hasta algún índice. A diferencia de los algoritmos tradicionales que minimizan la cantidad de comparaciones, la ordenación de panqueque requiere la menor cantidad de cambios posibles. El proceso se puede visualizar como una pila de panqueques , que se baraja tomando varios panqueques de arriba y dándoles la vuelta.

Algoritmo

El algoritmo más simple ( variante de clasificación por selección ) no da más vueltas, pero requiere encontrar el elemento más grande [1] . En 1979, Bill Gates y Christos Papadimitriou presentaron su algoritmo y probaron la suficiencia y necesidad de los flips [2] . En 1997, Heidari y Sudborog mostraron el límite inferior en . Proporcionaron valores exactos hasta , lo que requiere 15 vueltas [3] . Fue solo en 2008 que un grupo de investigadores de la Universidad de Texas en Dallas liderado por Sudborog [4] [5] logró superar significativamente (hasta ) el resultado de Gates y Papadimitriou .

Problema de panqueques quemados

Una versión más complicada es una especie de panqueque de una secuencia cuyos elementos contienen un parámetro binario adicional. Este problema fue propuesto por Bill Gates y Christos Papadimitriou en 1979 [2] . Se hizo conocido como el problema del panqueque quemado : 

Cada panqueque en la pila se quemó por un lado. Se requiere clasificar los panqueques en diámetro ascendente (descendente) para que todos queden en el plato con el lado quemado hacia abajo.

En 2007, un grupo de estudiantes creó una biocomputadora basada en E. coli modificada genéticamente que resolvió el problema de las tortitas quemadas . El papel de los panqueques lo desempeñaban fragmentos de ácido desoxirribonucleico (cuyos extremos 3' y 5' indicaban diferentes lados del panqueque). La bacteria, habiendo construido los fragmentos en el orden correcto, adquirió resistencia al antibiótico y no murió. El tiempo dedicado a buscar la combinación correcta mostró el número mínimo requerido de volteos de fragmentos [6] [7] .

Implementación

C# public static void PancakeSort < T >( IList < T > arr , int cutoffValue = 2 ) where T : IComparable { for ( int i = arr . Count - 1 ; i >= 0 ; -- i ) { int pos = i ; // Encuentra la posición del número máximo entre el comienzo y i for ( int j = 0 ; j < i ; j ++) { if ( arr [ j ]. CompareTo ( arr [ pos ]) > 0 ) { pos = j ; } } // ¿ya está en la posición correcta? if ( pos == i ) { continuar ; } // ¿está al principio de la matriz? Si no se voltea la sección de la matriz, entonces es if ( pos != 0 ) { Flip ( arr , pos + 1 ); } // Voltea la sección de la matriz para obtener el número máximo en la posición correcta Flip ( arr , i + 1 ); } } vacío estático privado Flip < T >( IList < T > arr , int n ) donde T : IComparable { for ( int i = 0 ; i < n ; i ++) { -- n ; Ttmp = arr [ i ] ; arr [ yo ] = arr [ n ]; matriz [ n ] = tmp ; } }

Notas

  1. ↑ Douglas B. Oeste. Los problemas de los panqueques (1975, 1979, 1973  ) Consultado el 16 de agosto de 2009. Archivado desde el original el 5 de abril de 2012.
  2. ↑ 1 2 William H. Gates; Christos H. Papadimitriou. Límites para clasificar por inversión de prefijo  //  Matemáticas discretas. - 1979. - Edicion. 27 . - Pág. 47-57 . Archivado desde el original el 10 de junio de 2007.
  3. ↑ Mohammad H. Heydari; I. Hal Sudborough. Sobre el diámetro de la red de panqueques  (inglés)  // Journal of Algorithms. - Duluth : Academic Press, Inc, 1997. - vol. 25 , edición. 1 . - Pág. 67-94 .
  4. ↑ El equipo supera al joven Bill Gates con una respuesta mejorada al llamado problema del panqueque en matemáticas  ( 17 de septiembre de 2008). Consultado el 16 de agosto de 2009. Archivado desde el original el 5 de abril de 2012.
  5. ↑ B. Chitturi, W. Fahle, Z. Meng, L. Morales, CO Shields, I. H. Sudborough, W. Voit. Un límite superior (18/11)n para clasificar por reversiones de prefijos  (inglés)  // Ciencias de la computación teórica. - Essex : Elsevier Science Publishers Ltd., 2009. - vol. 410 , edición. 36 . - Pág. 3372-3390 .
  6. ↑ Karmella A. Haynes, Marian L. Broderick, Adam D. Brown et al. Bacterias de ingeniería para resolver el problema del panqueque quemado  //  Revista de ingeniería biológica. - 2008. - Vol. 2 , edición. 8 _
  7. ↑ Video animado que explica la solución del problema por una computadora biológica  (inglés) . Consultado el 16 de agosto de 2009. Archivado desde el original el 5 de abril de 2012.

Véase también

Enlaces

  • Weisstein, Eric W. Clasificación  de panqueques . mundo matemático. Consultado: 16 de agosto de 2009.
  • Alejandro Bogomolny. Volteando  panqueques . Consultado el 16 de agosto de 2009. Archivado desde el original el 5 de abril de 2012.
 Algoritmos de clasificación
Teoría Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio
Elección
inserciones
fusión
sin comparaciones
híbrido
Otro
poco práctico