Устройство для сортировки чисел Советский патент 1987 года по МПК G06F7/06 

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

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

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

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

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

В регистры 1 -1„ заносятся сортируемые числа. После этого содержимое регистра 1„ сравнивается блоками сравнения со всеми остальными сортируемыми чис- лами, находящимися в регистрах Ь - l,,i. Блоки 2 сравнения выдают единичный сигнал лищь в том случае, если числа, находящиеся в соответствующих регистрах 1 (, 2,..., п-1), меньще числа, записанного в регистре „. Счетчик 4 подсчитывает количество блоков сравнения, имеющих единичный сигнал на своем выходе.

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

А АШЧ + К

где АНЛЧ - адрес области памяти, начиная с которого необходимо разместить отсортированные числа; К - количество чисел, меньших числа,

записанного в регистре 1„. Сумматор 5 вычисляет сумму Аиач-f- К.

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

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

0

5

Q

шает содержимое последнего на единицу. Эта операция приводит к тому, что на втором и последующих тактах числа, уже записанные в запоминающее устройство, участвуют в процессе сортировки уменьщенны- ми на единицу и, следовательно, число а2 ai будет размещено по адресау Анач-)-К-1. Это обеспечивает правильное формирование адресов и устранение «дыр в запоминающем устройстве при наличии в сортируемом массиве равных чисел.

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

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

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

Q

Устройство для сортировки чисел, содержащее п регистров, где п - количество сортируемых чисел, п-1 блоков сравнения, счетчик, сумматор, п групп по т элемен5 тов И, где т - количество разрядов сортируемых чисел, и группу из р выходных элементов И, где р Iog2/t , 1 X I - ближай- щее целое, большее х, причем выход /-го элемента И / -и группы, где г 1,2,...,т, j 1,2,...,(«-1), соединен с i-ы информационным входом (+1)-го регистра, выход /-го элемента И я-й группы является /-м ин- формационньЕм выходом устройства и соединен с /-М информационным входом первого регистра, выход г-го разряда /-го регистра соединен с первым входом /-го элемента И /-Й группы и с г -м входом первой группы /-ГО блока сравнения, выход которого соединен с /-М входом счетчика, /е-й выход которого, где k 1,2,...,р, соединен с fe-м входом первой группы сумматора, /г-й вход начального адреса устройства соединен с k-м входом второй группы сумматора, k-н выход которого соединен с первым входом k-ro выходного элемента И группы, выход которого является k-M адресным выходом устройства, выход /-ГО разряда п-го регистра соединен

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

0

5

0

5

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