Сортировка Джареда Даймонда :: Jared Diamond’s sort

Ружья, микробы и сталь
«Алгоритм», базирующийся на книге Джареда Даймонда (Jared Diamond) «Ружья, микробы и сталь: Судьбы человеческих цивилизаций» («Guns, Germs, and Steel: The Fates of Human Societies»).

Данное произведение, удостоенное Пулитцеровской премии, является очень значительным трудом по географической антропологии. Книгу высоко оценили социологи, историки и демографы. Под впечатлением от неё был и Билл Гейтс, не последний человек разбирающийся в глобальных мировых процессах: «Ошеломляет… Эта книга закладывает основы понимания истории человечества».

Ввиду обширности затрагиваемых аспектов, даже краткий пересказ изложенных в книге идей не представляется возможным в узких рамках этой небольшой статьи. Интересующиеся без труда смогут на просторах всемирной паутины найти саму книгу, а также 3-х серийный документальный фильм, снятый в 2005 году каналом National Geographic.

Алгоритм

Для каждого числа из сортируемого списка определим примитивную цивилизацию охотников-собирателей, регион их дислокации заселим дикими животными для последующего приручения и растениями для развития сельского хозяйства. Размер каждой локальной человеческой популяции, видовое разнообразие флоры и фауны — подбирать в прямой зависимости от соответствующего числа.

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

Сложность по времени

Время выполнения зависит только от величины наибольшего числа, что позволяет формально утверждать о временной сложности O(1). На данный момент известен только один достоверный случай использования данной сортировки, затраченное время составило примерно 13000 лет. Эта величина была бы меньше, если бы наибольший элемент в массиве был бы больше.

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

Название Сортировка Джареда Даймонда
(Jared Diamond’s sort, Diamond sort)
Автор Джаред Даймонд (Jared Diamond)
Год 1997
Класс Эзотерические сортировки
Устойчивость Нет
Сравнения Да
Сложность по времени Худшая O(1)
Средняя
Лучшая

Ссылки

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

DM’s Esoteric Programming Languages — Jared Diamond’s sort
Guns, Germs, and Steel on Wikipedia

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