La migliore risposta
Sleep sort è un algoritmo di ordinamento per scherzi che è diventato popolare su 4chan board / prog / [1]. Lo pseudocodice per lordinamento del sonno è:
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
Ah ah! Esilarante .
In altre parole, ciò che fa è che sleep sort genera un processo per ogni argomento. Ogni processo attende n secondi, quindi stampa n, il che significa che ci vuole 1 secondo per stampare “1”, 2 secondi per stampare out “2”, 100 secondi per stampare “100”. Ciò significa che per la maggior parte i numeri vengono stampati nellordine della loro dimensione, “ordinando” così gli argomenti.
La complessità di questo algoritmo in un mondo perfetto è O(max(args)), poiché saranno necessari max(args) secondi per stampare il arg più grande. In realtà, la complessità è O(n^2 + max(args)), perché il mantenimento di più processi in background si basa sul sistema operativo per gestire il cambio di contesto e la prioritizzazione dei processi, quindi lalgoritmo fondamentalmente esternalizza lordinamento effettivo a il kernel.
Si noti inoltre che non ci sono garanzie che loutput dellordinamento sia effettivamente corretto, una caratteristica che la maggior parte degli altri algoritmi di ordinamento non ha.
[1] http://dis.4chan.org/read/prog/1295544154
Risposta
Solo per divertimento, cè unimplementazione in Erlang
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Che può essere scritto bene anche come unespressione nella shell di Erlang
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].