Najlepsza odpowiedź
Sortowanie snu to algorytm sortowania żartów, który stał się popularny na forum 4chan / prog / [1]. Pseudokod sortowania podczas snu to:
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! Zabawne .
Innymi słowy, sortowanie uśpienia powoduje odrodzenie po jednym procesie dla każdego argumentu. Każdy proces czeka n sekund, a następnie wypisuje n, co oznacza, że wydrukowanie „1” zajmuje 1 sekundę, a wydrukowanie 2 sekundy wydrukowanie „2”, 100 sekund na wydrukowanie „100”. Oznacza to, że w przeważającej części liczby są drukowane w kolejności ich rozmiaru, co powoduje „sortowanie” argumentów.
Złożoność tego algorytmu w idealnym świecie to O(max(args)), ponieważ wydrukowanie największego arg zajmie max(args) sekund. W rzeczywistości złożoność jest O(n^2 + max(args)), ponieważ obsługa wielu procesów w tle zależy od systemu operacyjnego do zarządzania przełączaniem kontekstu i nadawania priorytetów procesom, więc algorytm zasadniczo zleca sortowanie jądro.
Zauważ również, że nie ma gwarancji, że dane wyjściowe są rzeczywiście poprawne, funkcja, której nie ma większość innych algorytmów sortowania.
[1] http://dis.4chan.org/read/prog/1295544154
Odpowiedź
Dla zabawy, w Erlangu jest implementacja
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Co można ładnie zapisać jako jedno wyrażenie również w powłoce Erlang
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].