Bästa svaret
Sovsortering är en skämtsorteringsalgoritm som blev populär på 4chan-kortet / prog / [1]. Pseudokoden för sömnsortering är:
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! Lustigt .
Med andra ord, vad det gör är att sömnsorter skapar en process för varje argument. Varje process väntar på n sekunder och skriver sedan ut n, vilket innebär att det tar 1 sekund att skriva ut ”1”, 2 sekunder att skriva ut ut ”2”, 100 sekunder för att skriva ut ”100”. Detta betyder att siffrorna för det mesta skrivs ut i storleksordningen, vilket ”sorterar” argumenten.
Komplexiteten hos denna algoritm i en perfekt värld är O(max(args)), eftersom det tar max(args) sekunder att skriva ut den största arg. I verkligheten är komplexiteten O(n^2 + max(args)), eftersom att upprätthålla flera bakgrundsprocesser är beroende av operativsystemet för att hantera kontextväxling och prioritering av processerna, så algoritmen lägger i princip ut den faktiska sorteringen till kärnan.
Observera också att det inte finns några garantier för att produktionen av sorteringen faktiskt är korrekt, en funktion som de flesta andra sorteringsalgoritmer inte har.
[1] http://dis.4chan.org/read/prog/1295544154
Svar
Bara för skojs skull finns 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 också kan skrivas fint som ett uttryck i Erlang-skalet
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].