ベストアンサー
スリープソートは、4chanボード/ prog / [1]で普及したジョークソートアルゴリズムです。スリープソートの擬似コードは次のとおりです。
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
ハハ！ 陽気な。
つまり、スリープソートは、引数ごとに1つのプロセスを生成します。各プロセスはn秒待機してから、nを出力します。つまり、「1」の出力に1秒、印刷に2秒かかります。 「2」を出力し、100秒で「100」を出力します。これは、ほとんどの場合、数値がサイズ順に出力されるため、引数が「ソート」されることを意味します。
完全な世界でのこのアルゴリズムの複雑さは、最大のargを印刷するのにmax(args)秒かかるため。実際には、複雑さはO(n^2 + max(args))です。これは、複数のバックグラウンドプロセスを維持するために、プロセスのコンテキスト切り替えと優先順位付けを管理するオペレーティングシステムに依存しているため、アルゴリズムは基本的に実際の並べ替えをカーネル。
また、ソートの出力が実際に正しいという保証はないことに注意してください。これは、他のほとんどのソートアルゴリズムにはない機能です。
[1] http://dis.4chan.org/read/prog/1295544154
回答
楽しみのために、Erlangに実装があります
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Erlangシェルでも1つの式として適切に記述できます
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].