베스트 답변
수면 정렬은 4chan 보드 / prog / [1]에서 인기를 얻은 농담 정렬 알고리즘입니다. 수면 정렬의 의사 코드는 다음과 같습니다.
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
하하! 재미있는 .
즉, 수면 정렬이 각 인수에 대해 하나의 프로세스를 생성한다는 것입니다. 각 프로세스는 n 초 동안 대기 한 다음 n를 인쇄합니다. 즉, “1”을 인쇄하는 데 1 초, 인쇄하는 데 2 초가 걸립니다. 출력 “2”, 100 초 출력 “100”. 즉, 대부분의 경우 숫자가 크기 순서대로 인쇄되므로 인수를 “정렬”합니다.
완벽한 세계에서이 알고리즘의 복잡성은 , 가장 큰 arg를 인쇄하는 데 max(args) 초가 걸립니다. 실제로 복잡성은 O(n^2 + max(args))입니다. 여러 백그라운드 프로세스를 유지하는 것은 운영 체제에 의존하여 프로세스의 컨텍스트 전환 및 우선 순위 지정을 관리하므로 알고리즘은 기본적으로 실제 정렬을 다음으로 아웃소싱합니다. 커널.
또한 정렬의 출력이 실제로 정확하다는 보장은 없으며 대부분의 다른 정렬 알고리즘에는없는 기능입니다.
[1] http://dis.4chan.org/read/prog/1295544154
Answer
재미를 위해 Erlang에 구현이 있습니다.
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Erlang 셸에서도 하나의 표현식으로 멋지게 작성할 수 있습니다.
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].