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

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обеспечения возможности сортировки массивов, содержащих равные числа. Устройство содержит регистр-счетчик, (п-1) регистров, где п - количество сортируемых чисел, (п-1) блоков сравнения. п групп элементов И, счетчик, сумматор, выходную группу элементов п и элемент задержки . Сортируемые числа записываются в регистры . Затем число из п-го регистра cpaL нивается блоками сравнения со всеми остальными числами. Счетчик подсчитывает количество чисел, меньших, чем содержаш,иеся в п-м регистре. К этому количеству сумматором прибавляется начальный адрес области памяти, в которую нужно занести отсортированный массив. После выдачи результата сортируемые числа сдвигаются по регистрам и затем анализируется число, ранее записанное в (п-1)-м регистре. При этом из числа, записываемого в регистр-счетчик, вычитается единица, что обеспечивает устранение «дыр в запоминаюш,ем устройстве при наличии в сортируемом массиве равных чисел. 1 ил. (О сл оо N3 СЛ 4 о: со

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

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

РЕСПУБЛИК дд 4 G 06 F 7 06

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

:4," /

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, „ »: и

Н А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ (21) 4049976/24-24 (22) 07. 04.86 (46) 23.07.87. Бюл. № 27 (72) А. С. Гуляев и В. В. Богданов (53) 681.325.5 (088.8) (56) Авторское свидетельство СССР № 981988, кл. G 06 F 7/06, 1980.

Авторское свидетельство СССР № 1290296, кл. G 06 F 7/06, 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — расширение функциональных возможностей за счет обеспечения возможности сортировки массивов, содержащих равные числа. Устройство содержит регистр-счетчик, (и — 1) регистров, где и — количество сортируемых чисел, (n — 1) блоков сравнения, ÄÄSUÄÄ 1325463 А 1 и групп элементов И, счетчик, сумматор, выходную группу элементов и и элемент задержки. Сортируемые числа записываются в регистры. Затем число из и-го регистра сраь нивается блоками сравнения со всеми остальными числами, Счетчик подсчитывает количество чисел, меньших, чем содержащиеся в

I и-м регистре. К этому количеству сумматором прибавляется начальный адрес области памяти, в которую нужно занести отсортированный массив. После выдачи результа-та сортируемые числа сдвигаются по регистрам и затем анализируется число, ранее записанное в (и — I )-м регистре. При этом из числа, записываемого в регистр-счетчик, вычитается единица, что обеспечивает устранение «дыр» в запоминающем устройстве при наличии в сортируемом массиве равных чисел. 1 ил.

1325463

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

1

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

Цель изобретения — расширение функциональных возможностей за счет обеспечения возможности сортировки массивов, содержащих равные числа, На чертеже представлена схема устройства.

Устройство содержит регистр-счетчик l I, регистры 1 — 1„ где п -- количество сортируемых чисел, блоки 2 — 2„, сравнения, группы из гпэлементов И 3I — 3„, где rn — количество разрядов сортируемых чисел, счетчик 4, сумматор 5, группу выходных элементов И 6, элемент 7 задержки, тактовый вход 8, вход 9 начального адреса, группу информационных 10 и адресных 11 выходов.

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

В регистры 1I — -l„заносятся сортируемые числа. После этого содержимое регистра 1„сравнивается блоками 2 — 2„ сравнения со всеми остальными сортируемыми числами, находящимися в регистрах 1I — 1„

Блоки 2 сравнения выдают единичный сигнал лишь в том случае, если числа, находящиеся в соответствующих регистрах 1е (1= — 1, 2,..., и — 1), меньше числа, записанного в регистре 1„. Счетчик 4 подсчитывает количество блоков сравнения, имеющих единичный сигнал на своем выходе.

С выхода счетчика 4 на один из входов сумматора 5 подается код количества сортирусмых чисел, меныпих числа, записанного в регистре 1. На второй вход сумматора 5 поступает код адреса области памяти, начиная с которого необходимо разместить отсортированный массив чисел. Тогда адрес ячейки памяти, по которому нужно записать число, находящееся в регистре l n, определяется как

А = А.<+К где А„„„— адрес области памяти, начиная с которого необходимо разместить отсортированные числа;

K, — количество чисел, меньших числа, записанного в регистре 1„.

Сумматор 5 вычисляет сумму А;.+ К.

По сигналу с тактового входа 8 устройства число, находящееся в регистре 1„, через открывшуюся группу элементов И 3 записывается в запоминающее устройство по адресу, выдаваемому сумматором 5 через группу выходIII>lx элемеHTon И 6.

Одновременно IIO этому же тактовому сигналу через группы элементов И 3, — 3 каждое пз сортируемых чисел, находящихся в рсгнсграх. 1I 1„, сдвигается в последуюгций регистр ио кольцу, и начинается второй такт работы устройства, на котором со всеми числами массива сравнивается число,первоначально находившееся в регистре l„ I При этом тот же тактовый иМпульс, поступая через элемент 7 задержки на вычитактщий вход регистра-счетчика 1, умень25

55 шает содержимое последнего на единицу.

Эта операция приводит к тому, что на втором и последующих тактах числа, уже записанные в запоминающее устройство, участвуктг в процессе сортировки уменьшенными на единицу и, следовательно, число а =

= a I будет размещено по адресау Апач+К вЂ” 1.

Это обеспечивает правильное формирование адресов и устранение «дыр» в запоминающем устройстве при наличии в сортируемом массиве равных чисел.

Дальнейшая работа устройства аналогична, Через и тактов в запоминающем устройстве, начиная с адреса, заданного на входе 9 устройства, будет записан отсортированный массив в порядке возрастания.

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

Устройство для сортировки чисел, содержащее и регистров, где n — количество сортируемых чисел, n — 1 блоков сравнения, счетчик, сумматор, п групп rro rn элементов И, где т — количество разрядов сортируемых чисел, и группу из р выходных элементов И, где р = — ) louden (, ) X (— ближайшее целое, большее х, причем выход -го элемента И j-й группы, где i= 1,2,...,т, j= 1,2,..., (n — 1), соединен сi-м информационным входом j+1)-го регистра, выход i-го элемента И и-й группы является i-м информационным выходом устройства и соединен с i-м информационным входом первого регистра, выход i-го разряда j-го регистра соединен с первым входом -го элемента И

1-й группы и с /-м входом первой группы

j-го блока сравнения, выход которого соединен с /-м входом счетчика, k-й выход которого, где k = 1,2,...,p, соединен с k-м входом первой группы сумматора, Й-й вход начального адреса устройства соединен с k-м входом второй группы сумматора, k-й выход которого соединен с первым входом k-го выходного элемента И группы, выход которого является k-м адресным выходом устройства, выход i-го разряда и-ro регистра соединен с i-ми входами второй группы всех блоков сравнения и с первым входом i-го элемента

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

1325463

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

Редактор В. Петраш Техред И. Верес Корректор Л. Таска

Заказ 3110/44 Тираж 672 Подписное

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

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

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