Bedste svar
Sleep sort er en vitsorteringsalgoritme, der blev populær på 4chan-kortet / prog / [1]. Pseudokoden til søvn sortering 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! Sjovt .
Med andre ord, hvad det gør er, at søvnsorter gyder en proces for hvert argument. Hver proces venter på n sekunder og udskriver derefter n, hvilket betyder, at det tager 1 sekund at udskrive “1”, 2 sekunder at udskrive ud “2”, 100 sekunder for at udskrive “100”. Dette betyder, at tallene for det meste udskrives i rækkefølgen af deres størrelse og dermed “sorterer” argumenterne.
Kompleksiteten af denne algoritme i en perfekt verden er O(max(args)), da det tager max(args) sekunder at udskrive den største arg. I virkeligheden er kompleksiteten O(n^2 + max(args)), fordi vedligeholdelse af flere baggrundsprocesser er afhængig af operativsystemet til at styre kontekstskift og prioritering af processerne, og algoritmen outsourcer grundlæggende den faktiske sortering til kernen.
Bemærk også, at der ikke er nogen garanti for, at outputen af sorteringen faktisk er korrekt, en funktion, som de fleste andre sorteringsalgoritmer ikke har.
[1] http://dis.4chan.org/read/prog/1295544154
Svar
Bare for sjov er der 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 pænt som et udtryk i Erlang-skallen
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].