malaya_zemlya, утащено оттуда и немного из комментов.Оказывается, чтобы вывести отсортированный по возрастанию массив натуральных чисел x[n], вовсе необязательно бегать по памяти, переставляя местами элементы, или заниматься другим сложным матаном. Достаточно сделать так (bash, числа передаются в командной строке):
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
waitЧто происходит? Да очень просто: для каждого элемента x[i] создаётся отдельный процесс, который ждёт x[i] миллисекунд, а потом выводит x[i]. Ясно, что первым на вывод пойдёт число с наименьшей задержкой, то есть наименьшее, ну и так далее :-)
Интересно, что:
- близкий к этому алгоритм реально используется, когда нужно отсортировать "не очень большие" числа. Создаётся массив z[] достаточного размера, заполненный нулями, далее для каждого x[i] делается z[x[i]]++, а потом просто пробегаем по z[] слева направо, вычитывая ненулевые элементы. Сложность - O(n+max(x[i])), расход памяти - O(max(x[i])).
- Время работы оригинального алгоритма - O(max(x[i])), а вот сложность (количество операций) - как бы вроде O(n) (чуть ниже я немного уточню). При этом в явном виде память не расходуется, а если учесть затраты памяти на создание процесса - получится O(n), что не так плохо для такого простого алгоритма.
- оказывается, есть платформа (линукс, конечно), умеющая выпадать в suspend (с выключением и последующим включением процессора) при простоях в работе более единиц миллисекунд(!). На такой платформе "процессорное время" (в тактах) окажется близким к "сложности вычислений" (пока процесс выполняет sleep, процессор выключен), то есть опять получится O(n).
На самом деле O(n) вряд ли получится - хотя в самой программе операций выполняется мало, реальной сортировкой придётся заниматься системному шедулеру, на который свалится n "задержек", и который будет вынужден "будить" процессы именно в нужном порядке. Но всё равно любопытно.
- также, «на лекции об финитизме (философское учение, отрицающее понятие бесконечного), время ответа Есенина-Вольпина на вопрос, существует ли какое-нибудь число, было пропорционально этому числу»