Дмитрий Радищев (dibr) wrote,
Дмитрий Радищев
dibr

сортировка

     Найдено у 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 "задержек", и который будет вынужден "будить" процессы именно в нужном порядке. Но всё равно любопытно.
        - также, «на лекции об финитизме (философское учение, отрицающее понятие бесконечного), время ответа Есенина-Вольпина на вопрос, существует ли какое-нибудь число, было пропорционально этому числу»
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments