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

 

Изобретение относится к вычислительной технике и может быть использовано в системах обработки данных. Целью изобретения является повьшение быстродействия при сортировке массива, содержащего равные числа. Устройство содержит распределитель импульсов, регистры, элементы сравнения , группы входных и выходных элементов И, счетчик, сумматор, регистр результата, дешифраторы, шифратор. генератор импульсов, элементы И, триггер управления, ассоциативные регистры, группы элементов И, ИЛИ, элементы запрета, задержки, элемент ИЛИ-НЕ. Как следует из изобретения, работа устройства состоит из двух этапов. На первом этапе путем последовательного сравнения содержимого соответствуницего регистра со всеми остальными определяется количество чисел, меньших размещенного в данном регистре, фиксируемого счетчиком в текущем цикле. Затем с помощью первого дешифратора определяется номер ассоциативного регистра, в который записывается двоичный код, номер анализируемого регистра. Этот код формируется шифратором из выходных сигналов распределителя импульсов, которые отражают номер цикла работы устройства, т.е. номер анализируемого регистра. 1 ил. с б (Л

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

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

РЕСПУБЛИК (19) (И>

А1 (50 4 G 06 F 7/06

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3772068/24-24 (22) 13.07.84 (46) 30.08.86. Бюл. Ф 32 (72) В.Г. Попов (53) 681.3(088,8) (56) Авторское свидетельство СССР

В 981988, кл. G 06 F 7/06, 1980.

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

9 1092494, кл. G 06 F 7/06, 1983. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки данных.

Целью изобретения является повышение быстродействия при сортировке массива, содержащего равные числа.

Устройство содержит распределитель импульсов, регистры, элементы сравнения, группы входных и выходных элементов И, счетчик, сумматор, регистр результата, дешифраторы, шифратор, генератор импульсов, элементы И, триггер управления, ассоциативные регистры, группы элементов И, ИЛИ, элементы запрета, задержки, элемент

ИЛИ-НЕ. Как следует из изобретения, работа устройства состоит из двух этапов. На первом этапе путем последовательного сравнения содержимого соответствующего регистра со всеми остальными определяется количество чисел, меньших размещенного в данном регистре, фиксируемого счетчиком в текущем цикле. Затем с помощью первого дешифратора определяется номер ассоциативного регистра, в который записывается двоичный код, номер анализируемого регистра. Этот код формируется шифратором из выходных сигналов распределителя импульсов, которые отражают номер цикла работы устройства, т.е ° номер анализируемого регистра. 1 ил.

1254467 этого производится поочередное сравнение чисел, и в ассоциативных регистрах 19 фиксируются номера регистров 2 так, что они отражают размещение чисел исходного массива в возрастающем порядке.

Пусть при n=-10 в регистрах мащен следующий массив чисел: а =5; а. =1; а„=2; а =6; а =5;

2 раза,=2; а =4 у У

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

Целью изобретения является повышение быстродействия при сортировке массива, содержащего равные числа.

На чертеже приведена функциональная схема устройства.

Устройство содержит распределитель 1 импульсов, регистры 2, элементы 3 сравнения, группы входных элементов И 4, группы выходных элементов И 5 и 6, счетчик 7, сумматор 8, регистр 9 результата, дешифратор 10, группу элементов ИЛИ 11, шифратор 12, элементы И 13, 14, триггер 15 управления, элемент И 16, генератор 17 импульсов, дешифратор

18, ассоциативные регистры 19, группы элементов И 20 переписи, группу элементов И 21, элемент 22 задержки, группу элементов ИЛИ 23, элементы

24 запрета, группы элементов И 25 результата, группу элементов ИЛИ 26, элемент ИЛИ-НЕ 27, выход 28 разрешения выдачи, вход 29 запуска, выходы

30, вход 31 разрешения выдачи, выход

32 конца работы, выходы 33, вход 34 задания начального адреса устройства.

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

Исходное состояние устройства характеризуется тем, что распределитель

1 импульсов, триггер 15 управления и регистры 19 установлены в состояние "0" (не показано).

Сортировка чисел устройством совместно с ЭВМ производится в два этапа.

На первом этапе после принятия исходного массива в регистры 2 и

А „ по входам 34 в сумматор 8 по

Нцц, сигналу "ПУСК, поступающему по входу 29, триггер 15 управления устанавливается в состояние "1". После открываются элементы И 4 и число из регистра 2< передается в регистр 9 результата и одновременно сравнивается со всеми числами, находящимися в регистрах 2 ...2,, в соответствующих элементах 3 ...3,0 сравнения. На выходах "Меньше" элементов 3 и 3 сравнения формируются единичные сигналы, а в счетчике 7 — значение N=2.

При этом на третьем выходе дешифратора 18 возникает единичный сигнал, открывающий элементы И 20 . Одновременно единичный сигнал с первого выl0 хода распределителей 1 поступает на шифратор 12, на выходе которого формируется двоичный код числа 1. Так как триггер 15 установлен в состояние "1", то двоичный код номера регистра 2;. т.е. выходные сигналы шифратора 12, записывается в регистр 19 .

По второму, очередному импульсу генератора 17 на втором выходе расДо поступления данного сигнала после того, как триггер 15 устанопределителя 1 формируется сигнал, и число а =-5 сравнивается во всех

25 элементах 3 сравнения, кроме 3.2.

При этом единичные сигналы на выходах Меньше формируют элементы

3,, Зз, 34, 3,, 38, и 3ч сравнения и аналогичным образом номер регистра 2 и так далее, т.е. двоичный код числа два будет записан в регистр 19, . Дальнейшая работа уст. ройства аналогична. По десятому импульсу с распределителя 1 в регистрах 19 будут записаны номера регистров 2, однозначно соответствующие возрастающему порядку размещения в них чисел. Так для указанного примера в регистрах 19 размещены сле4О дующие номера регистров 2: 19,=9;

19 =0; 19з=4; 194 =0; 19, =8; 19 =7; отражает порядок возрастания чисел — 1-7.

По сигналу с 10-го выхода распределителя очередным импульсом генера тора 17 устанавливается в "0" триггер 15, и элементом И 14 на выходе

28 формируется единичный сигнал, 56 как готовности устройства к выдаче отсортированного массива чисел. Од-. новременно устанавливается в "0" распределитель 1.

Второй этап работы устройства начинается при приходе сигнала на

Вход 31 .

1254467

20

3 вился в состояние "0", на выходах элементов ИЛИ 23 формируется следующий позиционный код в соответствии с содержимым регистров 19:

:1010111011. Посредством элементов запрета 24, соединенных по приоритетной схеме, этот код преобразуется в позиционный код следующего вида: 1000000000, так как единичным сигналом с выхода элемента ИЛИ 23 по инверсным входам закрываются элементы 24 запрета.

По единичному сигналу с выхода элемента ИЛИ 23< открываются элементы И 25, и двоичный код из регист-<5 ра 1",, т.е. код числа 9, через элементы И 25< и ИЛИ 26 поступает на дешифратор 10. Так как триггер 15 . находится в "0", то по входу управления дешифратор 10 открыт, и на его 9-м выходе формируется единичный сигнал, которым через элемент

ИЛИ 11 открыты элементы И 4 . Со— держимое регистра 2 через эти элементы передается в регистр 9 резуль- 25 тата, в котором фиксируется число а =1.

По .сигналу с входа 31 через элементы И 5 выдается двоичный код

А„ ц из сумматора 8 по выходам 33, 30 а через элементы И 6 на выходы 30— содержимое регистра 9 результата.

По адресу А<=А „ „ число а =1 записывается в ячейку внешней памяти.

Через время c, определяемое 3JIp. 35 ментом 22 задержки, устанавливается в "0" регистр 19, через открытый элемент И 21, . Одновременно в сумма-. тор 8 формируется очередной адрес

А =А<+ 1. Время < выбирается таким, чтобы обеспечить н<адежное считывание выходных сигналов элементов И 5, 6 р ЭВИ.

После установки в "0" регистра 45

19< на выходах элементов ИЛИ 23 фор.мируется позиционный код 0010111011, преобразуемый элементами И 24 в код

0010000000. Единичным сигналом с выхода элемента И 24 открываются 50 элементы И 25,< и содержимое регистра 19 >, т.е. двоичный код номера регистра 2. передается через элементы И 25 и ИЛИ 26 на дешифратор 10.

На четвертом выходе дешифратора 10 55 формируется единичный сигнал, который, через элемент ИЛИ 11 + открывает элементы И 4 4, и содержимое регистра

2 4 (а4=2) фиксируется в регистре 9 результата.

По импульсу с входа 31 код адреса А и двоичный код числа 2 из регистра 9 передается во внешнее устройство.

Через время < регистр 19 устанавливается в "0", и работа устрой ства затем аналогична рассмотренной выше.

По седьмому импульсу на входе 31 последнее число а<о =7 выдается во внешнее устройство и все регистры 19 оказываются в состоянии "0". При этом на выходе элемента И-HE 27 формируется единичный сигнал, поступающий по выходе 32 в качестве сигнала конца работы устройства во втором этапе.

При необходимости сортировки чисел в убывающем порядке исходный массив должен быть принят в регистры 2 в обратном коде.

Формула изобретения

Устройство для сортировки чисел, содержащее распределитель импульсов, регистров, « элементов сравнения, и групп входных элементов И, << --1 элементов запрета, счетчик, сумматор, две группы выходных элементов И, регистр результата, причем выходы < -ro регистра (<=1,2,...,п, где « — количество сортируемых чисел) соединены с первой группой входов

<-го элемента сравнения и с первыми входами соответствующих входных элементов И < -й группы, выходы которых соединены с 1 -й группой входов регистра результата и с (i+1) ми группами входов элементов сравнения соответственно с (i+1)-го по и -й, выходы входных элементов И j --й группы, где j =2,3,...,« соединены с

<-ми группами входов элементов сравнения соответственно с первого по (j -1)-й, выходы регистра результата соединены с первыми входами выходных элементов И первой группы, выходы которых являются выходами отсортированного числа устройства, выход не1 равенства < --ro элемента сравнениясоединен с i -м входом счетчика, вход задания начального адреса устройства подключен к первому входу сумматора, выходы которого соединены с первыми входами соответствующих выходных

S 1254 элементов И второй группы, выходы которых являются выходами адреса числа устройства, вторые входы выходных элементов И первой и второй групп подключены к входу разрешения выдачи результата устройства, g -е инверсные входы элементов запрета, где

9=1,2...,n 1, объединены, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия при сорти- 10 ровке массива, содержащего равные числа, в него введены два дешифратора, шифратор, и групп элементов И переписи, в групп элементов И результата, три группы элементов ИЛИ, груп- 15 па элеме*тов И, и ассоциативных регистров,- элемент задержки, триггер управления, три элемента И, элемент

ИЛИ-НЕ, генератор импульсов, выход которого соединен с первыми входами 20 первого и второго элементов И, второй вход первого элемента И подключен к прямому выходу триггера управления и первым входам элементов И переписи всех групп, а выход соеди- 25 нен с входом запуска распределителя

1 импульсов, -й выход которого соединен с первым входом i --го элемента

ИЛИ первой группы и с 1 -м входом шифратора, п -й выход распределите- g0 ля импульсов дополнительно подключен к первому входу третьего элемента И и второму входу второго элемента И, выход которого подключен к входу установки в "0" триггера управления, вход установки в которого является входом запуска устройства, инверсный выход которого соединен с инверсным входом элемента ИЛИ-НЕ, входом установки в "0" распределителя импульсов, уп-, равляющим входом первого дешифрато" ра и вторым входом третьего элемента И, выход которого является вйходом разрешения выдачи устройства, . 45

-й выход первого дешифратора соеди467 нен с вторым входом -го элемента

ИЛИ первой группы, выход которого подключен к вторым входам. входных элементов И -й группы, выходы разрядов счетчика соединены с соответствующими входами второго дешифратора, 1-й выход которого соединен с вторыми входами элементов И переписи -й группы, выходы которых подключены к информационным входам 1 -го ассоциативного регистра, выходы которого

1 соединены с входами > --го элемента

ИЛИ второй группы и с информационными входами элементов И результата

1-й группы, выходы которых подключены к входам соответствующих элементов ИЛИ третьей группы, выходы которых соединены с соответствующими входами первого дешифратора, выходы шифратора соединены с третьими входами соответствующих элементов И переписи всех групп, 1 -е инверсные входы каждого 8 -ro элемента запрета (1 =1,2,...,6; б =1,2,...,и-1) соединены с выходом j -ro элемента ИЛИ второй группы, выход первого элемента ИЛИ второй группы соединен с управляющими входами элементов И результата первой группы, с первым входом первого элемента И группы ц с первым входом элемента ИЛИ-НЕ, вы" ход g --ro элемента ИЛИ второй группы (g =2, 3,..., n) соединен с прямым входом ($-1)-ro элемента запрета и со -м входом элемента ИЛИ-НЕ, выход

5-го элемента запрета соединен с управляющими входами элементов И результата (5+1)-й группы и с первым входом (8+1)-го элемента И группы, вторые входы элементов И группы соединены с вторым входом сумматора и выходом элемента задержки, вход которого соединен с.входом разрешения выдачи устройства, выход элемента

ИЛИ-НЕ является выходом конца работы устройства. 1254467

Составитель Е. Иванова

Редактор Н. Слободяник Техред Л.Сердюкова Корректор В.Синицкая

Заказ 4721/52 Тираж 671 Подписное

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

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

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