Сортировка Джареда Даймонда :: 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