Tipo espagueti

El algoritmo de ordenación 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 un espacio de pila de O ( n ) de manera estable. Requiere un procesador paralelo, que se supone que puede encontrar el máximo de una secuencia de elementos en un tiempo de O ( 1 ).

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

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 más grande 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 por la mitad de manera que una pieza tenga una longitud de x unidades; deseche la otra pieza).
2. Una vez que tengas todos los palitos de espagueti, sujétalos con cuidado en el puño y bájalos a la mesa, de modo que queden de pie, apoyados sobre la superficie. Ahora, por cada palito, baja la otra mano desde arriba hasta que toque uno; este es claramente el más largo. Retira este palito e insértalo al principio de la lista de salida (inicialmente vacía) (o, de forma equivalente, colócalo en la última ranura sin usar de la matriz de salida). Repite el proceso hasta que hayas retirado todos los palitos.

Preparar los n espaguetis lleva tiempo lineal. Bajar los espaguetis a la mesa lleva tiempo constante, O ( 1 ). Esto es posible porque la mano, los espaguetis y la mesa funcionan como un dispositivo de computación totalmente paralelo . Hay entonces n espaguetis que retirar, así que, suponiendo que cada operación de contacto y retirada lleva tiempo constante, la complejidad temporal en el peor de los casos del algoritmo es O ( n ).

• Página principal de AK Dewdney
• Implementaciones de un modelo de clasificación física, Centro Boole para la Investigación en Informática
• Computación clásica/cuántica, Instituto IFF. Archivado el 19 de julio de 2011 en Wayback Machine.