Nejlepší odpověď
Třídění spánku je algoritmus třídění vtipů, který se stal populárním na palubě 4chan / prog / [1]. Pseudokód pro třídění spánku je:
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! Veselý .
Jinými slovy, to, co dělá, je to, že třídění spánku způsobí pro každý argument jeden proces. Každý proces čeká n sekund, poté vytiskne n, což znamená, že vytištění „1“ trvá 1 sekundu, tisk 2 sekundy out „2“, 100 seconds to print out „100“. To znamená, že čísla jsou z větší části vytištěna v pořadí podle jejich velikosti, čímž se „třídí“ argumenty.
Složitost tohoto algoritmu v dokonalém světě je O(max(args)), protože vytištění největších arg bude trvat max(args) sekund. Ve skutečnosti je složitost O(n^2 + max(args)), protože udržování více procesů na pozadí závisí na operačním systému, který řídí přepínání kontextu a stanovení priorit procesů, a proto algoritmus v podstatě zadává skutečné třídění jádro.
Upozorňujeme, že neexistují žádné záruky, že výstup řazení je ve skutečnosti správný, což je vlastnost, kterou většina ostatních třídicích algoritmů nemá.
[1] http://dis.4chan.org/read/prog/1295544154
Odpověď
Pro zábavu je implementace v Erlangu
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Které lze také pěkně napsat jako jeden výraz v prostředí Erlang
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].