Mejor respuesta
La clasificación de sueño es un algoritmo de clasificación de bromas que se hizo popular en el tablero de 4chan / prog / [1]. El pseudocódigo para la ordenación del sueño es:
procedure printNumber(n)
sleep n seconds
print n
end
for arg in args
run printNumber(arg) in background
end
wait for all processes to finish
¡Ja, ja! Hilarante .
En otras palabras, lo que hace es que la ordenación del sueño genera un proceso para cada argumento. Cada proceso espera n segundos, luego imprime n, lo que significa que tarda 1 segundo en imprimir «1», 2 segundos en imprimir imprimir «2», 100 segundos para imprimir «100». Esto significa que, en su mayor parte, los números se imprimen en el orden de su tamaño, «ordenando» los argumentos.
La complejidad de este algoritmo en un mundo perfecto es O(max(args)), ya que tomará max(args) segundos imprimir el arg más grande. En realidad, la complejidad es O(n^2 + max(args)), porque el mantenimiento de varios procesos en segundo plano depende del sistema operativo para administrar el cambio de contexto y la priorización de los procesos, por lo que el algoritmo básicamente subcontrata la clasificación real a el kernel.
También tenga en cuenta que no hay garantías de que la salida de la clasificación sea realmente correcta, una característica que la mayoría de los otros algoritmos de clasificación no tienen.
[1] http://dis.4chan.org/read/prog/1295544154
Respuesta
Solo por diversión, hay implementación en Erlang
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Que se puede escribir muy bien como una expresión en el shell de Erlang también
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].