stringtranslate.com

Clasificación de espaguetis

Diagrama esquemático de la clasificación de espaguetis. Los espaguetis se pueden clasificar sacándolos del paquete sobre la mesa en el orden en que sobresalen.

El ordenamiento espagueti es un algoritmo analógico de tiempo lineal para ordenar una secuencia de elementos, introducido por AK Dewdney en su columna de Scientific American . [1] [2] [3] Este algoritmo ordena una secuencia de elementos que requiere O ( n ) espacio de pila de manera estable. Requiere un procesador paralelo, que se supone que puede encontrar el máximo de una secuencia de elementos en tiempo O ( 1 ).

Algoritmo

Para simplificar, supongamos que estamos ordenando una lista de números naturales . El método de ordenación se ilustra utilizando espaguetis crudos :

  1. Para cada número x de la lista, obtenga una varilla de longitud x . (Una forma práctica de elegir la unidad es hacer que el número más grande m de la lista corresponda a una varilla completa de espagueti. En este caso, la varilla completa equivale a m unidades de espagueti. Para obtener una varilla de longitud x , parta una varilla en dos de modo que un trozo tenga una longitud de x unidades; descarte el otro trozo).
  2. Una vez que tengas todas las varillas de espagueti, tómalas sin apretarlas con el puño y bájalas hasta la mesa, de modo que todas queden en posición vertical, apoyadas sobre la superficie de la mesa. Ahora, para cada varilla, baja la otra mano desde arriba hasta que se encuentre con una varilla (esta es claramente la más larga). Retira esta varilla e insértala en la parte delantera de la lista de salida (inicialmente vacía) (o, equivalentemente, colócala en la última ranura sin usar de la matriz de salida). Repite hasta que se hayan quitado todas las varillas.

Análisis

Preparar las n barras de espagueti lleva un tiempo lineal. Bajar las barras sobre la mesa lleva un tiempo constante, O ( 1 ). Esto es posible porque la mano, las barras de espagueti y la mesa funcionan como un dispositivo informático totalmente paralelo . Hay entonces n barras para retirar, por lo que, suponiendo que cada operación de contacto y extracción lleva un tiempo constante, la complejidad temporal del algoritmo en el peor de los casos es O ( n ).

Referencias

  1. ^ Dewdney, AK (junio de 1984), "Sobre la computadora espagueti y otros aparatos analógicos para la resolución de problemas", Scientific American , vol. 250, núm. 6, págs. 19-26
  2. ^ Stauffer, Dietrich (15 de mayo de 1999), Reseñas anuales de física computacional VI , World Scientific , pág. 260, ISBN 981-02-3563-1
  3. ^ Adamatzky, Andrew (1 de julio de 2006), De computadoras utópicas a computadoras genuinamente no convencionales , Luniver Press, pág. 96, ISBN 0-9551170-9-7

Enlaces externos