Beste Antwort
Schlafsortierung ist ein Witzsortierungsalgorithmus, der auf dem 4chan-Board / prog / [1] populär wurde. Der Pseudocode für die Schlafsortierung lautet:
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! Urkomisch .
Mit anderen Worten, die Schlafsortierung erzeugt für jedes Argument einen Prozess. Jeder Prozess wartet auf n Sekunden und druckt dann n aus, was bedeutet, dass das Drucken von „1“ 1 Sekunde und das Drucken 2 Sekunden dauert „2“, 100 Sekunden, um „100“ auszudrucken. Dies bedeutet, dass die Zahlen größtenteils in der Reihenfolge ihrer Größe ausgedruckt werden, wodurch die Argumente „sortiert“ werden.
Die Komplexität dieses Algorithmus in einer perfekten Welt beträgt O(max(args)), da es max(args) Sekunden dauert, um das größte arg auszudrucken. In der Realität ist die Komplexität O(n^2 + max(args)), da die Verwaltung mehrerer Hintergrundprozesse vom Betriebssystem abhängt, um die Kontextumschaltung und Priorisierung der Prozesse zu verwalten, und der Algorithmus daher die eigentliche Sortierung grundsätzlich auslagert den Kernel.
Beachten Sie auch, dass es keine Garantie dafür gibt, dass die Ausgabe der Sortierung tatsächlich korrekt ist, eine Funktion, die die meisten anderen Sortieralgorithmen nicht haben.
[1] http://dis.4chan.org/read/prog/1295544154
Antwort
Nur zum Spaß gibt es eine Implementierung in Erlang
sort(L) ->
Parent = self(),
[ spawn\_link(fun() -> receive after X*10 -> Parent ! X end end) || X <- L ],
[ receive X -> X end || \_ <- L ].
Dies kann auch als ein Ausdruck in der Erlang-Shell geschrieben werden.
[ receive X -> X end
|| \_ <- [ spawn\_link(fun() -> receive after X*10 -> P ! X end end)
|| P <- [self()], X <- L ] ].