Методы программирования. Громов Ю.Ю - 93 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

93
Время работы алгоритма R равно 32N + 48М + 38 – 4Е, где N – число
исходных записей, М – основание системы счисления (число стопок), Е –
число встретившихся пустых стопок. Сравнение с другими алгоритмами,
построенными на основе аналогичных предположений (например, Алго-
ритм L. Сортировка посредством слияния списков), говорит явно в поль-
зу алгоритма R. Заметим, что если ключи уж очень длинные, поразрядная
сортировка не так эффективна, многие просмотры будут выполняться
почти впустую.
Упражнения
1. Выполните по алгоритму R поразрядную сортировку последова-
тельности из пятнадцати записей: (623 «к»), (390 «:»), (858 «обнажают-
ся»), (874 «ноги»), (379 «одеялу»), (555 «когда»), (47 «распутного»),
(12 «Достаток»), (701 «носу»), (589 «натянешь»), (841 «,»), (167 «равняет-
ся»), (322 «короткому»), (610 «его»), (905 «.») и установите содержимое
стопок после каждого из трёх просмотров, выполняемых при сортировке
этих записей с М = 10.
16. ВНЕШНЯЯ СОРТИРОВКА
Рассмотрим задачи, возникающие при внешней сортировке, т.е. в
случае, когда общий объём сортируемых записей превышает объём опе-
ративного запоминающего устройства. Внешняя сортировка принципи-
ально отличается от внутренней сортировки и это отличие объясняется
тем, что время доступа к файлам на внешних носителях информации жё-
стко лимитирует процесс. Структура данных должна быть такой, чтобы
сравнительно медленные периферийные запоминающие устройства (лен-
ты, диски, барабаны и т.д.) могли справиться с потребностями алгоритма
сортировки. Большинство изученных до сих пор методов внутренней
сортировки (вставка, обмен, выбор) фактически бесполезно для внешней
сортировки.
Предположим, например, что предназначенный для сортировки
файл последовательного доступа состоит из 5 000 000 записей R
1
R
2
…
R
5 000 000
. Рассмотрим случай, когда во внутренней памяти ЭВМ помеща-
ется только 1 000 000 из этих записей.
Сразу напрашивается такое решение: начать с сортировки каждого из
пяти подфайлов R
1
… R
1 000 000
, R
1 000 001
… R
2 000 000
, … , R
4 000 001
… R
5 000 000
по отдельности и затем слить полученные подфайлы. Отметим, слияние
оперирует только очень простыми структурами данных, а именно линей-
ными списками, пройти которые можно последовательным образом.
Заметим, что описанный процесс внешней сортировки, заключаю-
щийся во внутренней сортировке с последующим «внешним слиянием»,
является весьма популярным.

Страницы