Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 4
Текст из файла (страница 4)
Кроме того, данный метод устойчив по отношению к равным ключам. 11, Поразрядная сортировка с использованием алгоритма 5.2.5К вЂ” это не что иное, как сортировка списков, которая приемлема для ключей либо очень коротких, либо имеющих необычный порядок лексикографического сравнения.
Вместо ссылок можно применить распределяющий подсчет (п. 1 нашего обзора); такая процедура потребует пространства для 2Х записей и для таблицы счетчиков, но благодари простоте внутреннего цикла она особенно хороша для сверхбыстрых компьютеров— "пожирателей чисел', имеющих опережающее управление. (Предесшережение.
Поразрядную сортировку не следует использовать при малых Х!) 12. Сергиирвека методом вставок и слияния (см. раздел 5.3.1) наиболее приемлема при очень малых Ж в "прямолинейных" программах. Например, этот метод оказался бы подходящим в тех приложениях, в которых требуется сортировать много групп из пяти или шести записей. 13. Могут существовать и гибридные методы, объединяющие один или более из приведенных выше.
Например, короткие подфайлы. возникакнцие при быстрой сортировке, можно сортировать методом слияния и вставок, 14. И наконец, для реализации безымянного метода, встретившегося в ответе к упр. 5,2.1-3, требуется, по-видимому, кратчайшая из возможных программ сортировки. Но среднее время работы такой программы пропорционально К~, т.
е. это самая медленная программа сортировки из упомянутых в данной книге! Пространственные и временные характеристики многих из этих методов, запрограммированных для компьютера й1Х, сведены в табл. 1. Важно иметь в виду, что числа в данной таблице являются лишь грубымп оценками относительного времени сортировки. Они применимы только к одному компьютеру, и предположения., касающиеся исходных данных, далеко не для всех программ абсолютно правомерны.
Сравнительные таблицы, подобные этой, приводились во многих работах, но не найдется таких двух авторов, которые пришли бы к одинаковым выводам! Тем ие менее данные о времени работы позволяют оценить хотя бы порядок скорости, которую следует ожидать от каждого алгоритма при сортировке записей из одного слова, так как ИХХ вЂ” довольно типичный компьютер, В столбце "Память" в табл. 1 содержится некоторэл информация об объеме вспомогательной памяти, используемой каждым алгоритмом, в единицах длины записи. Здесь буквой е обозначена доля записи, необходимая для одного поля связи; так, например, .К(1 + с) означает, что методу требуется пространство для Л записей и К полей связи. В асимптотических оценках среднего и максимального времени, приведенных в табл.
1, учитываются только главные члены, доминнрующне при больших К в предположении случайных исходных данных; с обозначает произвольную константу. Эти формулы могут иногда ввести в заблуждение, поэтому указано также фактическое время выполнения программы для двух конкретных последовательностей исходных данных. Случай Х = 16 относится к шестнадцати клк>чам, так часто появлявшимся в примерах раздела 5.2, а случай К = 1000 относится к последовательности Км Кю- . *К~ооо определенной формулами Кгош = 0; К„~ = (3141592621К„+ 211314865Ц шо610'э. Для получения характеристик каждого алгоритма,, представленного в таблице, использовалась достаточно совершенная программа для й1Х, как правило, учитывающая усовершенствования, которые описаны в упражнениях.
Размер байта при выполнении этих программ принят равным 100. Длл внешней сортировки необходимы методы, отличакнциеся от методов внутренней сортировки, потому что предполагается использование сравнительно простых структур данных и большое внимание уделяется уменьшению времени ввода- вывода. В разделе 5.4.6 рассматриваются интересные методы, разработанные для сортировки данных на магнитных лентах, а в разделе 5.4.9 обсуждается использование дисков и барабанов.
Конечно, сортировка — не единственная тема этой главы. Попутно мы много узнали о том, как работать со структурами данных, обращаться с внешней памятью, анализиРовать алгоритмы, и о том, как изобретать... новые алгоритмы. Где упоминается Таблица 1 срлвнкник мктодов внутркннкй сортировки нримкнитрльно к Ркллиэлции нл комныоткрк 812 «х и «« Время вмполнеиия «к Р 6$ Метод Д й Ср.,щ М 51=!ба=1000 При Сравнение и подсчет Распределение и подсчет Простая вставка Сортировка с убываощим смещением Вставка в список Вставка в несколько списков Обменная сортировка со слиянием Обменная сортировка с разделением Сортировка методам медиаим из трех ключей Обменная поразрядная сортировка Простой вмбор Пирамидальная "юр™рокка Слияние списков Поразрядная сортировка списков 2.5Ж~ 433 3.5!«7 645 1248615 Ь, с 35246 Ь, с, Г, ! 1.25«Уг + 13.25)т ,0175Ж~ + 18% 4«х'(!8 г«)х 939 284366 > 2Кз 470 > 5! 487 81486 272 Л' 1Ь35 137614 3 25Л«х 853 24.5Ж 1п Л«1068 2.5Ж~ + 3«з«' !и ««« 23.08Л«1п Ф+ 0.01% 2525287 159714 104716 Ь, с, 1 36838 Ь, с 14.437г'!в Ф+ 4.925« 327«': + 4838 44 «"««(1 + с) 36 57+ е(!У + 200) Прог, 5.2.4Ь Да Прог.
5.2,5В. Да 14.4Ж 1в Ж 761 32Ф 4250 Упр. 5.2-5 Да 22 «У(1+ г) Упр. 5.2-9 Да 26 2!У+ 1000г Упр. 5.2Л-ЗЗ Да 10 !У+ 1 Прог. 5.2ЛП Нет 21 7««+ г 18 5! Упр. 5.2Л-ЗЗ Да 19 «ч«'(1+ с) Про«. 5.2.1М Нет 18 Ф + с(«У + 100) Упр. 5.2.2 — 12 Нет 35 ««« Прог. 5.2.211 Нет 63 Ж+ 2«18г7 Упр. 5,2,2-55 Нет 100 57+2с!87«~ Прог 5 2 2В. Нет 45 Л« -~-68с Прог. 5.2.38 Нет Ьб «««' Прог. 5.2.3Н Нет 30 «У 4~„г+ 5.55«'~ 1065 3992432 22!Ч + 10010 22)У 10362 32010 5!««в + 9 5 Л, 3«х~ 412 1491928 3.9Ф™ + 10)9 18 д«+ 1665! сл1~«~ 567 128758 2.87557(!8 Ф)з 11.67Ю 1и ««« — 1.74% 10.63««* )и «У + 2.12«У 14.43!У М «7+ 23.9««' Примечания к тпабл.
1 а Ключи только из трех цифр Ь Клк>чи только из шести цифр (т. е. из трех байтов) с Вывод не перекомпоновал; результирующая последовательность определяется неявно ссылками или счетчиками 6 Смещение выбирается, как в 5.2.1-(11); несколько лучшая последовательность появляется в упр. 5.2.1-29 е М = 9, если использовать 333; для варианта с 01Ч добавить к среднему времени выполнения 1.ба 1 М = 100 (размер байта) 3 М = 34, так как 2зэ > 10~о > 2зз Ь Поскольку теория неполная, данные о среднем времени получены эмпирически 1 Оценка среднего времени базируется на предположении о равномерном распределении ключей ) Дальнейшее совершенствование программы, о котором упоминается в тексте раздела н упражнениях, относящихся к этой программе, могут уменьшить время выполнения Ранние разработки.
Поиск прототипов современных методов сортировки возвращает нас в 19 век, когда были изобретены первые машины для сортировки. В Соединенных Штатах Америки перепись всех граждан проводилась каждые 10 лет, и уже к 1880 году проблема, связанная с обработкой огромных по объему данных переписи стала очень острой, В самом деле, число одиноких (т. е. не состоящих в браке) граждан не подсчитывалось ежегодно, хотя вся необходимая информация собиралась.
Герман Холлерит (Негшап Но!!егЫЬ), двадцатилетний служащий Бюро переписи, изобрел остроумный электрический табулятор, отвечакхций нуждам сбора статистики, и около ста его машин успешно использовались при обработке данных переписи 1390 года. Иа рис. 94 изображен первый аппарат Холлерита, приводимый в действие от аккумуляторных батарей, Для нас основной интерес представляет "'сортировальный ящик" справа, который открыт для того, чтобы можно было увидеть половину из 26 внутренних отделений. Оператор вставлял перфокарту размером 6'~ х 3-' дюймов в "пресс" н опускал рукоятку; это приводило к тому, что закрепленные на пружинах штыри на верхней палелн в тех местах, где на карте пробиты отверстия, входят а контакт с ртутью на нижней панели.
В результате замыкания соответствующей электрической цепи показание связанного с ней циферблата изменялось на 1 и, кроме того, одна из 26 крышек сортировального ящика открывалась. В этот момент оператор отпускал пресс, клал карту в открытое отделение и закрывал крышку. Однажды через эту машину пропустили 19 071 карту за одни 6;„'-часовой рабочий день (в среднем около 49 карт в минуту!). (Средний оператор работал примерно втрое медленней.) Население продолжало неуклонно расти, и первые табуляторы-сортнровшики оказались недостаточно быстрыми, чтобы справиться с обработкой данных переписи 1900 года.
Поэтому Холлернт изобрел еще одну машину, чтобы предотвратить еще один кризис в обработке данных. Его новое устройство (запатентованное в 1901 и 1904 годах) автоматически подавало карты и выглядело, в сущности, почти так Рис. 94. Табулятор Холлернтв. (Фотография любезно предоставлена архивам 1ВМ.) же, как современные карточные сортировальные машины, История ранних машин Холлерпта с интересными полробни;тами изложена Леоном Э, Трусделлом (1еоп Е. ТтиевдеИ) в кинге ТЬе Петейзршелс оу Рплсй Сагд Таба!асюп (%аапй181оп: 1'. 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
