Beste svaret
Sleep sort er en vitsesorteringsalgoritme som ble populær på 4chan board / prog / [1]. Pseudokoden for søvnsortering er:
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! Morsom .
Med andre ord, hva det gjør er at søvnsorter gyter av en prosess for hvert argument. Hver prosess venter på n sekunder, og skriver deretter ut n, noe som betyr at det tar 1 sekund å skrive ut «1», 2 sekunder å skrive ut ut «2», 100 sekunder for å skrive ut «100». Dette betyr at tallene for det meste skrives ut i størrelsesorden, og dermed «sorterer» argumentene.
Kompleksiteten til denne algoritmen i en perfekt verden er O(max(args)), da det tar max(args) sekunder å skrive ut den største arg. I virkeligheten er kompleksiteten O(n^2 + max(args)), fordi å opprettholde flere bakgrunnsprosesser er avhengig av at operativsystemet styrer kontekstsvitsjing og prioritering av prosessene, og algoritmen legger derfor ut den faktiske sorteringen til kjernen.
Vær også oppmerksom på at det ikke er noen garanti for at utdataene til sorteringen faktisk er riktige, en funksjon som de fleste andre sorteringsalgoritmer ikke har.
[1] http://dis.4chan.org/read/prog/1295544154
Svar
Bare for moro skyld er det implementering i Erlang
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Som også kan skrives pent som ett uttrykk i Erlang-skallet
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].