Устройство для сортировки чисел

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (51)4 G 0 F 08

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3973260/24-24 (22) 10. 11.85 (46) 23. 05. 88. Бюл. N 19 (72) А.А.Мельник, Е.Я. Ваврук и И.Г.Цмоць (53) 681.325 (088.8) (56) Авторское свидетельство СССР

N- 637810, кл. G 06 F 7/08, 1976.

Авторское свидетельство СССР

N 1007099, кл. G 06 F 7/08, 1981. (54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ, содержащее m ячеек анализа, где ш — количество чисел в выходном массиве, каждая ячейка содержит приемный регистр, блок сравнения, регистр результата и коммутатор, причем информационный вход устройства соединен с информационным входом приемного регистра первой ячейки, выход приемного регистра i-й ячейки, где i = 1,2, ° ..,m соединен с информационным входом регистра результата и первыми информационными входами блока сравнения и коммутатора той же ячейки анализа, выход регистра результата i-й ячейки анализа соединен с вторыми информационными входами коммутатора и блока сравнения той же ячейки анализа, выход блока сравнения i-й ячейки анализа соединен с управляющим входом коммутатора и первым входом разрешения записи регистра результата той же ячейки анализа, выход коммутатора j-й ячейки анализа, где j = 1,2,...,(m-1), соединен с информационным входом приемного регистра (j+1) и ячейки анализа, выход коммутатора m-й ячейки анализа является выходом устройства, тактовый вход устройства соединен с входами разрешения записи приемных регистров всех ячеек анализа и с вторыми входами разрешения записи регистров результата всех ячеек анализа, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при сортировке нескольких массивов чисел, каждая ячейка анализа дополнительно содержит первый и второй триггеры, причем синхровходы триггеров всех, ячеек анализа подключены к тактовому входу устройства, прямой выход первого триггера каждой ячейки анализа соединен с управляемым входом блока сравнения и информационным входом второго триггера той же ячейки анализа, прямой выход второго триггера

j-й ячейки анализа соединен с информационным входом первого триггера (3+1)-й ячейки анализа, вход начала массива устройства соединен с информационным входом первого триггера первой ячейки анализа, прямой выход второго триггера m-й ячейки анализа является выходом окончания сортировки массива устройства.

1397900

Изобретение относится к автоматике и вычислительной технике.

Цель изобретения — повышение быстродействия при сортировке нескольких массивов чисел.

На чертеже приведена схема устройства.

Устройство содержит m ячеек анализа 1,-1, где ш — количество чисел в выходном массиве. Каждая ячейка содержит приемный регистр 2, регистр

3 результата, блок 4 сравнения, коммутатор 5, триггеры 6 и 7. Устройство содержит также информационный вход 8, вход 9 начала массива, тактовый вход 10, информационный вход 11 и выход 12 окончания сортировки массива.

Устройство работает следующим образом.

На вход 8 устройства последовательно поступают числа сортируемых массивов. Каждое число сопровождается импульсом на тактовом входе 10, а 25 первое число каждого массива — сигналом логической единицы на входе 9.

Поэтому первое число массива записывается в регистр 21, а триггер 6, устанавливается в единичное состояние.30

Единичный сигнал с выхода триггера

6 1, поступающий на управляющий вход блока 4 сравнения, предопределяет перезапись в следующем такте числа из регистра 3 q через коммутатор 5 в регистр 2, а из регистра 2, — в регистр 31 независимо от соотношения чисел, хранящихся в регистрах 2, и

3,. Единица из триггера 6, переписы— вается при этом в триггер 7 . В третьем такте происходит сравнение чисел, находящихся в регистрах 2 и 3,, большее из них переписывается через коммутатор 51 в регистр 2 (число из которого переписывается в регистр 3 ) а меньшее остается в регистре 31. В регистр 2 1 при этом записывается следующее число. Дальнейшая работа устройства аналогична.

Таким образом, большие по величине числа продвигаются к m-й ячейке, не перезаписываясь в регистры 3,-3 поэтому "обгоняют" меньшие числа.

На выходе 11 формируется. последовательность отсортированных чисел.

Сразу за загрузкой в регистр nocll леднего числа первого массива а

1 1 может быть загружено, не ожидая окончания процесса сортировки первого массива первое число второго масси2 ва а,. При этом единичное значение в тр .ггерах 6,-6, продвигаясь по

Гт цепочке ячеек одновременно с числом

2 1 а,, запрещает сравнение чисел а и ъ а тем самым исключая воэможность э перемешивания чисел из разных массивов. Конец сортировки очередного массива фиксируется наличием единичного сигнала на выходе 12 устройства.

Составитель В. Горохов

Редактор И. Николайчук Те хред Л. Олийнык Корректор А.Тяско

Заказ 227 1/47 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4