Сортировка "демона Максвелла" :: Maxwell's demon sort
Метод сортировки основанный на "мысленном эксперименте" предложенном великим английским физиком XIX века Джеймсом Клерком Максвеллом. Данный способ аппаратно реализовать, опираясь на текущие достижения науки и техники, достаточно проблематично.
Демон Максвелла
Ёмкость с газом разделена на две половины непроницаемой стенкой. В стенке есть отверстие, которое снабжено специальным устройством, которое назовём демоном Максвелла. Демон устроен так, что через отверстие он из левой части в правую пропускает только быстрые (горячие) молекулы газа, а из правой в левую - медленные (холодные) молекулы.
В результате функционирования данной системы якобы возникает парадокс, нарушающий Второе начало термодинамики: в сосуде исключительно за счёт внутренней энергии, без привлечения дополнительной, охлаждается левая часть и нагревается правая.
Алгоритм
Возьмём сосуд с газом и рассмотрим все молекулы как неотсортированный набор чисел (каждое из которых - некое отображение энергии молекулы). Перегородим сосуд стенкой со встроенным в неё демоном Максвелла. Через некоторое время в правой части сосуда соберутся молекулы, чья энергия превышает некоторую заданную величину (или равна ей), а в левой части - молекулы, чья энергия меньше этой величины.
Разделим каждую половину сосуда на свои половинки с помощью стен со встроенными демонами Максвелла (для которых заданы другие пропускные значения). Таким образом мы дополнительно распределим молекулы на ещё более "горячие" и "холодные". И так мы дополнительными стенками со встроенными демонами Максвелла будем делить пространство внутри сосуда до тех пор, пока в каждой его ограниченной части не будут молекулы с одинаковой энергией. В этот момент все частицы окажутся "отсортироваными".
Характеристики алгоритма
| Название | Сортировка "демона Максвелла" (Maxwell's demon sort) | |
|---|---|---|
| Год | 1867 | |
| Класс | Эзотерические сортировки | |
| Сложность по времени | O(n! + [n/2]! + [n/4]! + [n/8]! + ... + 1!) | |
| Сложность по памяти | O(n) | |
Ссылки
Эзотерические сортировки Дэвида Морган-Мара
DM's Esoteric Programming Languages - Demon sort
Демон Максвелла