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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

100
Таблица 4
Содержимое памяти Вывод
503 87 512 61 61
503 87 512 908 87
503 170 512 908 170
503 897 512 908 503
(275) 897 512 908 512
(275) 897 653 908 653
(275) 897 (426) 908 897
(275) (154) (426) 908 908
(275) (154) (426) (509) (конец отрезка)
275 154 426 509 154
275 612 426 509 275
677 612 426 509 426
677 612 765 509 509
677 612 765 703 612
677
∝
765 703 677
∝ ∝
765 703 703
∝ ∝
765
∝
765
∝ ∝ ∝ ∝
(конец отрезка)
Доказано, что для случайных входных данных ожидаемая длина от-
резков равна 2Р. Однако во многих практических приложениях входные
данные нельзя считать полностью случайными, если в них уже существу-
ет определённый порядок. Следовательно, отрезки, порождаемые выбо-
ром с замещением, имеют тенденцию содержать даже больше, чем
2Р записей. Поскольку время, нужное для внешней сортировки слиянием,
в значительной степени зависит от количества отрезков, порождаемых
начальной распределительной фазой, то выбор с замещением становится
особенно привлекательным. Другие способы внутренней сортировки по-
рождали бы примерно вдвое больше начальных отрезков, поскольку раз-
меры памяти ограничены.
Теперь детально рассмотрим процесс создания начальных отрезков
посредством выбора с замещением. Следующий алгоритм включает в
себя прекрасный способ начального формирования дерева выбора и раз-
деления записей, принадлежащих разным отрезкам, а также вывода по-
следнего отрезка по единообразной и сравнительно простой логике. За-
метим, что надлежащая обработка последнего отрезка, порождённого
выбором с замещением, оказывается довольно сложной и часто бывает
камнем преткновения для программиста.
Основная идея заключается в том, чтобы рассматривать каждый
ключ как пару (S, K), где K – первоначальный ключ, а S – номер отрезка,

Страницы