Meilleure réponse
Le tri du sommeil est un algorithme de tri des blagues qui est devenu populaire sur le tableau 4chan / prog / [1]. Le pseudocode pour le tri de sommeil est:
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
Ha-ha! Hilarant .
En dautres termes, ce quil fait, cest que le tri de sommeil engendre un processus pour chaque argument. Chaque processus attend n secondes, puis imprime n, ce qui signifie quil faut 1 seconde pour imprimer « 1 », 2 secondes pour imprimer out « 2 », 100 secondes pour imprimer « 100 ». Cela signifie que pour la plupart, les nombres sont imprimés dans lordre de leur taille, « triant » ainsi les arguments.
La complexité de cet algorithme dans un monde parfait est O(max(args)), car il faudra max(args) secondes pour imprimer le plus grand arg. En réalité, la complexité est O(n^2 + max(args)), car le maintien de plusieurs processus darrière-plan repose sur le système dexploitation pour gérer le changement de contexte et la hiérarchisation des processus, et donc lalgorithme sous-traite essentiellement le tri réel à le noyau.
Notez également quil ny a aucune garantie que la sortie du tri soit réellement correcte, une fonctionnalité que la plupart des autres algorithmes de tri nont pas.
[1] http://dis.4chan.org/read/prog/1295544154
Réponse
Pour le plaisir, il y a une implémentation dans Erlang
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Qui peut aussi bien être écrit comme une seule expression dans le shell Erlang
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].