Сортировка по числовым ключам

16-08-2013, 17:17
Просмотров: 345
Если процесс начинается с сортировки по младшему разряду и кончается сортировкой по старшему, с сортировкой всей колоды при каждом прогоне, весь процесс потребует совершения прогонов, где есть число разрядов в заданном ключе. После того как этот процесс упорядочения адресов будет закончен, соответствующие элементы информации могут быть в нужном порядке переписаны во внешнее запоминающее устройство.

Сортировка по числовым ключам


Весьма изящным методом сортировки по числовым ключам является так называемый метод «упорядочения по адресам», применяемый на вычислительных машинах с хранимой программой. Если, например, в десятичной вычислительной машине необходимо упорядочить последовательность машинных слов по двухразрядному ключу, значения которого не повторяются, то этот ключ может быть использован в качестве индекса для изменения адреса ячейки, в которую помещается каждый элемент информации.
Так, если результаты упорядочения заданного массива информации будут записываться в ячейки оперативной памяти накопителя от 1900 до 1999, тогда, если значение двухразрядного ключа есть 65, элемент информации, соответствующий этому значению, будет заслан в ячейку 1965. Если элементы информации, подлежащей упорядочению, являются более длинными (длиннее одного машинного слова), то тот же метод может быть применен для упорядочения адресов элементов информации (а может быть и самих элементов). В случае совпадения значений ключей для различных элементов информации, если только эти совпадения сравнительно редки, можно дополнительно вводить признак появления исключительного случая.
В случае использования запоминающих устройств на магнитной ленте сортировка по (десятичному) числовому ключу может быть выполнена путем считывания с одной ленты и записи результата на одну из десяти лент, каждая из которых соответствует одной из возможных цифр данного разряда ключа.

Источник: delete-it
Автор: Николай Максименко
Опубликовано пользователем: 805 (смотреть все)
Комментарии:
» » » Сортировка по числовым ключам