Cel mai bun răspuns
Sortarea somnului este un algoritm de sortare a glumelor care a devenit popular pe placa 4chan / prog / [1]. Pseudocodul pentru sortarea somnului este:
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! Hilarious .
Cu alte cuvinte, ceea ce face este că sortarea somnului generează un proces pentru fiecare argument. Fiecare proces așteaptă n secunde, apoi imprimă n, ceea ce înseamnă că durează 1 secundă pentru a tipări „1”, 2 secunde pentru a imprima scoateți „2”, 100 de secunde pentru a imprima „100”. Aceasta înseamnă că, în cea mai mare parte, numerele sunt tipărite în ordinea mărimii lor, astfel „sortând” argumentele.
Complexitatea acestui algoritm într-o lume perfectă este O(max(args)), deoarece va dura max(args) secunde pentru a imprima cel mai mare arg. În realitate, complexitatea este O(n^2 + max(args)), deoarece menținerea mai multor procese de fundal se bazează pe sistemul de operare pentru a gestiona comutarea contextului și prioritizarea proceselor, astfel algoritmul externalizează practic sortarea reală nucleul.
De asemenea, rețineți că nu există garanții că rezultatul sortării este de fapt corect, o caracteristică pe care majoritatea celorlalți algoritmi de sortare nu o au.
[1] http://dis.4chan.org/read/prog/1295544154
Răspuns
Doar pentru distracție, există implementare în Erlang
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Care poate fi scris frumos ca o expresie și în shell-ul Erlang
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].