Сортировка «демона Максвелла» :: Maxwell’s demon sort

Джеймс Клерк Максвелл
Метод сортировки основанный на «мысленном эксперименте» предложенном великим английским физиком XIX века Джеймсом Клерком Максвеллом. Данный способ аппаратно реализовать, опираясь на текущие достижения науки и техники, достаточно проблематично.

Демон Максвелла

Ёмкость с газом разделена на две половины непроницаемой стенкой. В стенке есть отверстие, которое снабжено специальным устройством, которое назовём демоном Максвелла. Демон устроен так, что через отверстие он из левой части в правую пропускает только быстрые (горячие) молекулы газа, а из правой в левую — медленные (холодные) молекулы.

Демон Максвелла

В результате функционирования данной системы якобы возникает парадокс, нарушающий Второе начало термодинамики: в сосуде исключительно за счёт внутренней энергии, без привлечения дополнительной, охлаждается левая часть и нагревается правая.

Алгоритм

Возьмём сосуд с газом и рассмотрим все молекулы как неотсортированный набор чисел (каждое из которых — некое отображение энергии молекулы). Перегородим сосуд стенкой со встроенным в неё демоном Максвелла. Через некоторое время в правой части сосуда соберутся молекулы, чья энергия превышает некоторую заданную величину (или равна ей), а в левой части — молекулы, чья энергия меньше этой величины.

Разделим каждую половину сосуда на свои половинки с помощью стен со встроенными демонами Максвелла (для которых заданы другие пропускные значения). Таким образом мы дополнительно распределим молекулы на ещё более «горячие» и «холодные». И так мы дополнительными стенками со встроенными демонами Максвелла будем делить пространство внутри сосуда до тех пор, пока в каждой его ограниченной части не будут молекулы с одинаковой энергией. В этот момент все частицы окажутся «отсортироваными».

Быстрая сортировка

Сортировка «демона Максвелла» уместно рассматривать как своеобразную «термодинамическую» интерпретацию быстрой сортировки.

Опорный элемент, с которым сравниваются элементы — это пропускное значение демона Максвелла. Происходит одновременный просмотр массива слева и справа, маленькие («холодные») элементы перебрасываются в начало отрезка (в левую часть сосуда), большие («горячие») — в конец (в правую часть сосуда).

Двухсторонний просмотр сходится в некоторой точке -это и есть окончательная стенка, разделяющая массив-сосуд на 2 замкнутые области с «горячими» и «холодными» эелементами-молекулами. Затем над этими областями рекурсивно производятся аналогичные действия.

Характеристики алгоритма

Название Сортировка «демона Максвелла» (Maxwell’s demon sort)
Год 1867
Класс Эзотерические сортировки
Сложность по времени O(n! + [n/2]! + [n/4]! + [n/8]! + … + 1!)
Сложность по памяти O(n)

Ссылки

Хабрахабр: Эзотерические сортировки Дэвида Морган-Мара

DM’s Esoteric Programming Languages — Demon sort
Демон Максвелла в Википедии

Добавить комментарий