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

Изобретение относится к автомат ке и вычислительной технике и може быть использовано в специализированных вычислительных мал1инах и ус ройствах обработки данных. По основному авт. св. № 981988 известно устройство для сортировки чисел, содержащее распределитель импульсов,m регистров, m элементов сравнения, m групп элементов И счетчик, сумматор и регистр резуль тата, причем выходы -1-го ( i 1, 2, .. . ,tri ) регистра соединены с пе вой группой входов i-го элемента сравнения и с первыми входами элементов И i-й группы, выходы которых соединены с i-й группой входо регистра результата с ( i -й)-ми группами входов элементов сравнени с первого по (1-1)-й и с i -ми гру пами входой элементов сравнения с (i + 1)-го по т-й, первьй управляющий вход устройства является вх дом распределителя импульсов, каждый i-и выход которого соединен с вторыми входами элементов И й группы, выход 1-го элемента сравнения соединен с i-м входом счетчика, выходы которого соединены с первой группой входов сумматора, в рая группа входов которого соедине на с группой информационных входов устройства, а выходы - с первыми входами элементов И первой выходной группы, выходы которых являются первой группой выходов устройства, первые входы элементов и вто рой выходной группы соединены с выходами регистра результата, а выходы являются второй группой выходов устройства tllНедостатком данного устройства являются ограниченные функциональные возможности, так как оно не позволяет сортировать массив чисел содержащий равные элементы, В случае, если в массиве находятся К равных чисел, то для них устройством определяется один и тот же адрес области памяти, куда они должны быть помещены. Поэтому все эти числа будут записаны по одному адресу оставив незаполненньими предыдущие К-1 ячеек. Таким образом, из | равных чисел при сортировке потеряно К-1 число. Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения возможности сортировки массива, содержащего равные числа. Поставленная цель достигается тем, что в устройство для сортировки чисел введены т-1 элементов запрета, где т- количество сортируемых чисел, причем прямой вход i-го ( i 1, 2, .„.,m-l) элемента запрета подключен к выходу Равно (i + 1)го элемента сравнения, а выход соединен с (т+ О-м входом счетчика, 2m-и вход которого подключен к выходу Равно первого элемента сравнения, i-й выход распределителя импульсов (i 1, 2, ...Ш -1) соединен с i-ми инверсными входами элементов запрета с i-ro по (т-1)-и включительно. На чертеже приведена схема устройства. Устройство содержит распределитель 1 импульсов, группу регистров , группу элементов 3 -3 сравнения, группы , 5 и 6 элементов И, счетчик 7, сумматор 8, регистр 9 результата, управляющие входы 10 и 11, группу 12 информационных входов, группы 13 и 14 информационных выходов и группу элементов 15-|- 15 запрета. Устройство работает следующим образом. В регистры 2 заносятся сортируемые числа, в регистр 9 результата - нуль, а распределитель 1 импульсов устанавливается в начальное состояние (на схеме не показано). После этого устройство готово К сортировке чисел в порядке возрастания. Теперь на вход 10 устройства подается первый тактовьй сигнал, по которому появляется импульс на первом выходе распределителя 1 импульсов. При- этом открывается первая группа 4 элементов И и число из перого регистра 2 переписывается в регистр 9 результата и одновременно этим подается на соответствующие руппы входов элементов 32- 3 сравения, которыми оно сравнивается о всеми остальными сортируемыми ислами. Сигнал Меньше на выходах лементов 3 сравнения появляется ишь в том случае, если числа, наодящиеся в соответствующем регисте 2, меньше числа, поступаемого на вторые входы элемента 3 сравнения через группы 4 элементов И. В случае равенства числа из первого регистра 2 нескольким числам на выходах Равно соответствукнцих эле ментов сравнения появляются сигналы Эти сигналы поступают на схему приоритета, состоящую из элементов 15 запрета. В данном случае сигналом с первого выхода распределителя 1 импульсов все элементы 15 запрета зак ты. Счетчик 7 подсчитывает количест поступающих сигналов с элементов 3 сравнения, т.е. подсчитывает количество чисел, которые меньше, чем вьщеленное-распределителем t импуль сов и записанное в регистр 9 резуль тата с учетом порядкового номера этого числа среди равных чисел. Это число поступает на первую группу входов сумматора 8, а на его вторую группу входов - код адреса области памяти, начиная с которого необходимо разместить отсортированный мас сив чисел. Тогда адрес области памя ти, по которому следует записать число, находящееся в регистре 9 результата, определяется следующим образом: ( , адрес области памяти, на чиная с которого необходимо разместить отсортированные числа-, количество чисел, меньших числа, записанного в регистре 9 результатаj порядковый номер числа среди равных чисел в мас сиве. Сумматор 8 вычисляет сумму (-N + K- 1. По сигналу-на управляющем входе 11 устройства число, находящееся в регистре 9 результата, переписывается в запоминаю944щее устройство по адресу, находящемуся в сумматоре 8. Следующий такт работы устройства начинается с подачи следующего тактового сигнала на вход 10 устройства. При этом появляется импульс на следующем выходе распределителя 1 импульсов, который открывает следующую группу 4,, элементов И, вследствие чего в регистр 9 результата переписывается число из следующего регистра 22 и одновременно с этим осуществляется сравнение этого числа с остальными числами. Если второе число равно первому, то элемент 3 сравнения, соответствующий первому регистру 2-J,выдаст сигнал равенства, который поступит на вход счетчика 7. Если в массиве сортируемых чисел окажутся еще числа, равные второму числу, импульсы с соответствующих элементов 3 сравнения не поступят на вход счетчика 7, так как 15,- 15 запвсе остальные элементы 3 т-1 рета будут закрыты импульсом с второго выхода распределителя 1 импульсов. В дальнейшем устройство работает аналогично описанному. Для сор.тировки чисел в порядке убывания необходимо в регистры 2 записать инверсные коды сортируемых чисел. Таким образом, предлагаемое устройство по сравнению с известным имеет более широкие функциональные возможности, так как позволяет сортировать массивы чисел, содержащие равные числа. Введение в схему элементов запрета и использование дополнительных выходов Равно элементов сравнения позволяет изменять адреса равных чисел таким образом, что эти числа располагаются подряд в ячейках памяти, благодаря чему в предлагаемом устройстве исключается потеря К-1 числа в сортируемом массиве, содержащем К равных чисел.

г

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ по авт. св. № 981988, о тличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности сортировки массива, содержащего равные числа, в него введены n-l элементов запрета, где т- количество сортируемых чисел, причем прямой вход 1-го ( 1 1, 2, ..., trrt) элемента запрета подключен к выходу Равно ( л + 1)-го элемента сравнения, а выход соединен с (tri-ь i )-м входом счетчика, 2rv-n вход которого подключен к выходу Равно первого элемента сравнения, -к выход распределителя импульсов ( i 1, 2 , . .. , rn-l) соединен с i-ми инверсными входами элементов запрета с i-ro по (т-1)-й включительно.

/5