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

Изобретение относится к автоматике и вычислительной.техршке и может быть использовано в специализированribix мапшнах и устройствах обработки данных. .Известно устройство для сортировки уисел, содержащее m регистров, выходы которых соединены с входами схем сравнения, другие выходы которых подключены к выходам регистра реэультата, выходы схем сравнения соединены через переключатель с входами элемента ИЛИ, элементы И, триггер, УЗЛЫ запрета и временной распределитель 11 . Недостатком этого устройства является низкое быстродействие, Наиболее близким по технической сущности к предлагаемому является устройство для сортировки mп-разрядных чисел, содержащее распределитель импульсов, п регистров, п схем сравнения, . группы элементов И, счетчик, сумматор, регистр результата, причем выходы разрядов каждого i-ro регистра где ,2, .,., п, соединены с соответствуюащми информационными входами первой группы i-й схемы сравнения и 1-й группы элементов И, виходы которых подключены к входам i-группы регистра результата, а каждый i-й выход распределителя импульсов соеди нен с управляющим входом элементов И i-й группы, выходы регистра результата подключены к информационным вхо дам второй группы всех схем сравнения и к информационным входам первых выходных элементов И группы, выход каж дой i-й схемы сравнения соединен с i-M входом счетчика, выходы которого подключены к входам первой группы сумматора, входы второй группы которого соединены с входными шинами уст ройства, а выходы - с информационными входами выходных элементов И второй группы элементов, управляющие входы выходных элементов И первой и второй групп подкл лчены к управляюще шине устройства СЗ. Однако, если среди сортируемого массива имеются одинаковые числа, то на выходе устройства они формируются с одним и тем же адресом. Таким обра зом, в-запоминающем устройстве будет записан отсортированный, массив чисел с недостающими членами. Например, если имеется пять равных чисел, то их значение будет записано только по одному первому адресу, а четыре пропущено с сохранением предьщущих значений ячеек, что приведет к невозможности дальнейшей обработки г.ассива. Цель изобретения - безошибочное формирование упорядоченного массива чисел. Указанная цель достигается тем, что в устройство для сортировки чисел, содержащее распределитель импульСов, п регистров, п блоков сравнения, группы элементов И, счетчик, сумматор регистр результата, причем выходы разрядов каждого i-ro регистра, где , 2, ..., п, соединены соответствующими информационными входами первой группы i-ro блока сравнения и i-й группы элементов И, выходы которьк подключены к входам i-й группы регистра результата, выходы разрядов которого подключены к информационным входам второй группы всех блоков сравнения и к информационным входам выходных элементов И первой группы, выходы которых являются информационными выходами устройства, а управляющие входы первых выходных элементов И подключены к шине разрешения выдачи числа устройства и управляющим входам выходньк элементов И второй группы, выходы которых являются выходами адреса блока памяти устройства, а информационные входы соединены с соответствующими выходами сумматора, входы первой группы которого соединены с входами задания адреса области памяти устройства, а входы второй группы - с выходами разрядов счетчика, каждый i-й выход распреде- . лителя импульсов подключен к управляющим входам элементов И i-й группыjj введены п триггеров, п элементов И и п элементов ИЛИ, причем каждый i-й выход распределителя импульсов соединен с входом установки в единичное состояние i-ro триггера, выхрд которого подключен к первому входу i-ro элемента И, выход которого соединен с первым входом i-ro элемента ИЛИ, а второй вход - с выходом Равно блока сравнения, выход Меньше которого подключен к второму входу i-ro элемента ИЛИ, выход которого соединен с соответствующим входом счетчика. На чертеже представлена схема предлагаемого устройства. Устройство содержит распределитель 1 импульсов, п регистров 2, п схем 3 сравнения, регистр 4 результата, группы 5-6 элементов И, сумматор 8, счетчик 9, входы 10 и 11 устройства вход 12 управления устройства, выходы 13 и 14 устройства, п триггеров 15, п элементов И 16, п элементов ИЛИ 17.

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

В регистры 2 заносятся сортируемые числа, регистр 4 результата и триггеры 15 устанавливаются в нуль, а распределитель 1 импульсов - в исходное состояние (не показано). После этого устройство готово к сортировке чисед в порядке возрастания.

Затем на вход 10 устройства подается первый тактовых сигнал, по которому появляется сигнал на первом (верхнем) выходе распределителя 1 импульсов. При этом верхний триггер 15 установится в единичное состояние, сигнал с которого разрешает прохождение сигнала с выхода Равно схемы 3 сравнения через элементен l6. Также открьшается группа 6 элементов И и число из верхнего регистра 2 перезаписьшается в верхний регистр 4 результата. Это число сравнивается со всеми сортируемыми числами в схемах 3 сравнения. Если число в каком-либо регистре 2 меньше числа, находящегося в регистре 4 результата, то на вьгходе Меньше соответствующей схемы 3 сравнения появляется сигнал, если числа равны, то сигнал появляется на выходе Равно. Сигнал с выхода Равно поступит через элементы И 16 и ИЛИ 17 на счетчик 9 только при наличии разрешакнцего сигнала с триггера 15, т.е. дпя чисел ранее сравниваемых со всеми (включая число сравниваемое в текущем такте). Счетчик 9 подсчитывает количество схем 3 сравнения, имеющих сигнал на своем выходе.

Таким образом, с дохода счетчика 9 на один из входов сумматора 8 подается код количества сортируемых чисел, меньших или равных (но ранее сравниваемых со всеми) числу, записанному в регистре 4 результата. На второй вход сумматора 8 подается уменьшенный на единицу код адреса области памяти, начиная с которого необхо-. димо разместить отсортированную информацию. Тогда адрес области памяти, по которому следует записать число, находящееся в регистре 4 результата, определяется соотношением

-1) + N,

(А

нем

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

N - число чисел, меньших или равных, но ранее сравниваемых со всеми, числу, записанному в регистре результата.

Сумматор 8 вычисляет сумму (А(,ц -1) + N. По сигналу на входе 12 устройства число, находящееся в регистре 4 результата, записывается в запоминакщее устройство по адресу, выдаваемому сумматором 8.

Второй такт работы устройства начинается с подачи второго тактового сигнала на вход 10 устройства. При этом появляется сигнал на втором выходе распределителя 1 импульсов, который устанавливает в единичное состояние соответствукяций триггер 15 и открывает соответствунлцую группу элементов И, вследствие чего в регистр 4 результата перезаписывается число из регистра 2. Дальнейшая работа устройства аналогична рассмотренному После того как устройство отработает Тактов, в запоминающем устройстве будет записан отсортированный массив чисел по адресу, заданному на входе t1 устройства. Для сортировки чисел в порядке убывания необходимо 6 регистры 2 записать инверсные значения кодов сортируемых чисел.

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

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее распределитель лмпульсов, и регистров, п блоков сравнения, группы элементов И, счетчик, сумматор регистр результата, причем выходы разрядов каждого i-ro регистра, где , 2, ..., п, соединены с соответствующими информационными входами первой группы i-ro блока сравнения и i-и группы элементов И,выходы которых подключены к входам i-й группы регистра результата, выходы разрядов которого подключены к информационным входам второй группы всех блоков сравнения и к информационным входам выходных элементов И первой группы,выходы которых являются информационными выходами устройства, a управляющие входы первых выходных элементов И подключены к шине разрешения выдачи числа устройства и управляющим входам выходных элементов И второй группы, выходы которых являют ся выходами адреса блока памяти устройства, a информационные входы соединены с соответствующими выходами сумматора, входы первой группы которого соединены с входами задания адреса области памяти устройства a входы второй группы - с выходами разрядов счетчика, каяздый i-й выход распределителя импульсов подключен к управляющим входам элементов И i-й группы, отличающееся тем, что, с целью повышения достоверности записи массива путем исключения потерь информации при записи одинаковых чисел, в устройство введе- ны п триггеров, п элементов И и п элементов ИЛИ, причем каждый i-й выход распределителя импульсов с единен с входом установки в единичное состояние i-ro триггера, выход которого подключен к первому входу i-ro элемента И, выход которого соединен с первым входом i-ro элемента ИЛИ, a второй вход - с выходом Равно блока сравнения, выход Меньше которого подключен к второму входу i-ro 00 элемента ИЛИ, выход которого-соединен с соответствующим входом счетчика.