Legjobb válasz
Az alvási rendezés egy viccek rendezési algoritmusa, amely népszerűvé vált a 4chan táblán / prog / [1]. Az alvási rend pszeudokódja:
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! Vidám .
Más szavakkal, más szavakkal azt jelenti, hogy az alvásfajta minden argumentumhoz egy folyamatot hoz létre. Minden folyamat n
másodpercet vár, majd kinyomtatja a n
-t, vagyis 1 másodperc, 2 másodperc a nyomtatás “2”, 100 másodperc a “100” kinyomtatásához. Ez azt jelenti, hogy a számok többnyire a méretük szerinti sorrendben kerülnek kinyomtatásra, ezzel “rendezve” az argumentumokat.
Ezen algoritmus összetettsége egy tökéletes világban O(max(args))
, mivel max(args)
másodpercekbe telik a legnagyobb arg
kinyomtatása. A valóságban a bonyolultság O(n^2 + max(args))
, mert a több háttérfolyamat fenntartása az operációs rendszerre támaszkodik a kontextusváltás és a folyamatok rangsorolásának kezelésében, ezért az algoritmus alapvetően kiszervezi a tényleges rendezést a kernel.
Vegye figyelembe azt is, hogy nincs garancia arra, hogy a rendezés kimenete valóban helyes, ez a tulajdonság a legtöbb más rendezési algoritmusnak nincs.
[1] http://dis.4chan.org/read/prog/1295544154
Válasz
Csak szórakozásból van megvalósítás az Erlang
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Amely szépen írható egy kifejezésként az Erlang shellbe is
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].