Beste antwoord
Slaapsortering is een algoritme voor het sorteren van grappen dat populair werd op het 4chan-bord / prog / [1]. De pseudocode voor slaapsortering is:
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! Hilarisch .
Met andere woorden, wat het doet, is dat slaapsortering één proces voor elk argument voortbrengt. Elk proces wacht n seconden en drukt vervolgens n af, wat betekent dat het 1 seconde duurt om “1” af te drukken, 2 seconden om af te drukken out “2”, 100 seconden om “100” af te drukken. Dit betekent dat de getallen voor het grootste deel worden afgedrukt in de volgorde van hun grootte, waardoor de argumenten worden “gesorteerd”.
De complexiteit van dit algoritme in een perfecte wereld is O(max(args)), aangezien het max(args) seconden duurt om de grootste arg af te drukken. In werkelijkheid is de complexiteit O(n^2 + max(args)), omdat het onderhouden van meerdere achtergrondprocessen afhankelijk is van het besturingssysteem om de contextomschakeling en prioritering van de processen te beheren, en daarom besteedt het algoritme in feite het daadwerkelijke sorteren uit aan de kernel.
Merk ook op dat er geen garanties zijn dat de uitvoer van de sortering werkelijk correct is, een functie die de meeste andere sorteeralgoritmen niet hebben.
[1] http://dis.4chan.org/read/prog/1295544154
Antwoord
Gewoon voor de lol, er is implementatie in Erlang
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Wat ook mooi als een uitdrukking in de Erlang-shell kan worden geschreven
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].