Sleep sort es un algoritmo de clasificación de broma que se hizo popular en la placa 4chan / prog / [1]. El pseudocódigo para ordenar por sueño es:
procedimiento printNumber (n)
dormir en segundos
imprimir n
fin
para arg en args
ejecuta printNumber (arg) en el fondo
fin
esperar a que terminen todos los procesos
¡Jaja! Hilarante .
En otras palabras, lo que hace es que el tipo dormir genera un proceso para cada argumento. Cada proceso espera n segundos, luego imprime n , lo que significa que demora 1 segundo para imprimir “1”, 2 segundos para 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, por lo tanto “ordenando” los argumentos.
La complejidad de este algoritmo en un mundo perfecto es O(max(args)) , ya que tomará max(args) segundos para imprimir el arg más grande. En realidad, la complejidad es O(n^2 + max(args)) , porque mantener múltiples procesos en segundo plano depende del sistema operativo para gestionar el cambio de contexto y la priorización de los procesos, por lo que el algoritmo básicamente subcontrata la clasificación real al núcleo.
También tenga en cuenta que no hay garantías de que la salida del género 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/1…