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

ОЮЭ СОВЕТСНИХСОЦИАЛ ИСТИЧЕСНИРЕСПУБЛИК 4 19) (И)5 у С 06 Р 7/ АНИЕ ИЗОБРЕТЕНИЯ Н АВТОРСНОМ ЕЛЬС Цыганков ОРТИРОВКИо тчто, сц ных воз" ния воза, содер ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЭОБРЕТЕНИЙ И ОТНРЦТИЙ(54) (57) УСТРОЙСТВО ДЛЯ ЧИСЕЛ по авт. св. В 98198 л и ч а ю щ е е с я тем, лью расширения функционал можностей за счет обеспеч можности сортировки масси жащего равные числа, в него введень вэлементов запрета, где т - количество сортируемых чисел, причем прямой вход 1-го ( 1 = 12 тг 1) элемента запрета подключен к выходу "Равно" (+ 1)-го элемента сравнения, а выход соединен с1(п 1+)-м входом счетчика, 2 ю-и вход которого подключен к выходу "Равно" первого элемента сравнения, 1-й выход распределителя импульсов ( 1 = 1, 2, ,п) соединен с 1-ми инверсными входами элементов запрета с 1-го по Ьп)-й включительно.92494 2 ства за счет обеспечения воэможнос 10Изобретение относится к автоматике и вычислительной технике и можетбыть использовано в специализированных вычислительных машинах и устройствах обработки данных,По основному авт. св. У 981988известно устройство для сортировкичисел, содержащее распределительимпульсов, о регистров, р элементов сравнения, н групп элементов И,счетчик, сумматор и регистр результата, причем выходы 1 -го ( 1 = 1,2, ,в ) регистра соединены с первой группой входов 1 -го элементасравнения и с первыми входами элементов И 1-й группы, выходы которых соединены с -й группой входоврегистра результата с ( 1 -й)-мигруппами входов элементов сравненияс первого по (1-1)-й и с 1 -ми группами входов элементов сравнения с(1 + 1)-го по т-й, первый управляющий вход устройства является входом распределителя импульсов, каждый 1 -й выход которого соединен 25с вторыми входами элементов И 1 -йгруппы, выход 1-го элемента сравнения соединен с 1-м входом счетчика, выходы которого соединены спервой группой входов сумматора, вто- ЗОрая группа входов которого соединена с группой информационных входовустройства, а выходы - с первымивходами элементов И первой выходной группы, выходы которых являют 35ся первой группой выходов устройства, первые входы элементов и второй выходной группы соединены свыходами регистра результата, авыходы являются второй группой выходов устройства 13. ти сортировки массива, содержащегоравные числа.Поставленная цель достигаетсятем, что в устройство для сортировки чисел введены щ -1 элементов запрета, где е - количество сортируемых чисел, причем прямой вход-го(= 1, 2, , щ -) элемента запрета подключен к выходу "Равно(1 + 1)-го элемента сравнения, авыход соединен с (пз + 1)-м входомсчетчика, 2 щ -й вход которого подключен к выходу Равно 1 первогоэлемента сравнения 1 -й выходраспределителя импульсов (1 = 1, 2,ш - 1) соединен с 1-ми инверсными входами элементов запрета с1-го по (щ)-й включительно,На чертеже приведена схема устройства.Устройство содержит распределитель 1 импульсов, группу регистров2-2 , группу элементов 31-3 сравнения, группы 41-4 , 5 и 6 элементов И, счетчик 7, сумматор 8, регистр 9 результата, управляющиевходы 10 и 11, группу 12 информационных входов, группы 13 и 14 информационных выходов и группу элементов 15- 15 запрета.Устройство работает следующим образом.В регистры 2 заносятся сортируемые числа, в регистр 9 результата - нуль, а распределитель 1 импульсов устанавливается в начальное состояние (на схеме не показано), После этого устройство готовок сортировке чисел в порядке возрастания, Недостатком данного устройства являются ограниченные функциональные возможности, так как оно не позволяет сортировать массив чисел, содержащий равные элементы. В спучае, если в массиве находятся К равных чисел, то для них устройством определяется один и тот же адрес области памяти, куда они должны быть помещены. Поэтому все эти числа будут записаны по одному адресу, оставив незаполненными предыдущие К ячеек. Таким образом, из К равных чисел при сортировке потеряно К - 1 число.Цель изобретения - расширение функциональных возможностей устройТеперь на вход 10 устройства подается первый тактовый сигнал, по которому появляется импульс на первом выходе распределителя 1 импульсов. При этом открывается первая группа 4 элементов И и число из первого регистра 2 переписывается в регистр 9 результата и одновременно с этим подается на соответствующие группы входов элементов 3 - 3 срав 2 п нения, которыми оно сравнивается со всеми остальными сортируемыми числами. Сигнал "Меньше на выходах элементов 3 сравнения появляется лишь в том случае, если числа, находящиеся в соответствующем регистре 2, меньше числа, поступаемогона вторые входы элемента 3 сравнения через группы 4 элементов И. В случае равенства числа из первого регистра 2 нескольким числам на выходах "Равно" соответствующих элементов сравнения появляются сигналы.Эти сигналы поступают на схему приоритета, состоящую из элементов 15 запрета. В данном случае сигналом с первого выхода распределителя 1 им О пульсов все элементы 15 запрета закрыты. Счетчик 7 подсчитывает количество поступающих сигналов с элементов 3 сравнения, т.е. подсчитывает количество чисел, которые меньше, чем 1 выделенное распределителем 1 импульсов и записанное в регистр 9 результата с учетом порядкового номера этого числа среди равных чисел. Это число поступает на первую группу 20 входов сумматора 8, а на его вторую группу входов - код адреса области памяти, начиная с которого необходимо разместить отсортированный массив чисел. Тогда адрес области памя", ти, по которому следует записать число, находящееся в регистре 9 результата, определяется следующим образом:307 -начгде А - адрес области памяти, наНдцчиная с которого необходимо разместить отсортированные числа;35М - количество чисел, меньших числа, записанногов регистре 9 результата;К - порядковый номер числасреди равных чисел в массиве.Сумматор 8 вычисляет суммуАч Мк. По сигналу.на управляющем входе 11 устройства число, 4 находящееся в регистре 9 результата, переписывается в запоминающее устройство по адресу, находящемуся в сумматоре 8. Следующий такт работы устройства начинается с подачи следующего тактового сигнала на вход 10 устройства. При этом появляется импульс на следующем выходе распределителя 1 импульсов, который открывает следующую группу 4 элементов И, вследствие чего в регистр 9 результата переписывается число из следующего регистра 2 и одновременно с этим осуществляется сравнение этого числа с остальными числами. Если второе число равно первому, то элемент 31 сравнения, соответствующий первому регистру 2,выдаст сигнал равенства, который поступит на вход счетчика 7. Если в массиве сортируемых чисел окажутся еще числа, равные второму числу, импульсы с соответст. вующих элементов 3 сравнения не поступят на вход счетчика 7, так как все остальные элементы 15 - 15 зап 3 п- рета будут закрыты импульсом с второго выхода распределителя 1 импульсов. В дальнейшем устройство работает аналогично описанному,Для сортировки чисел в порядке убывания необходимо в регистры 2 записать инверсные коды сортируемых чисел.Таким образом, предлагаемое устройство по сравнению с известным имеет более широкие функциональные возможности, так как позволяет сортировать массивы чисел, содержащие равные числа. Введение в схему элементов запрета и использование дополнительных выходов "Равно" элементов сравнения позволяет изменять адреса равных чисел таким образом, что эти числа располагаются подряд в ячейках памяти, благодаря чему в предлагаемом устройстве исключается потеря К числа в сортируемом массиве, содержащем К равных чисел.5/32 Тираж ИПИ Государственног по делам изобретени 35, Москва, Ж, Ра исное ПоСССР митет открытикая наб. дилиал П 11 П "Патент", г. Ужгород, ул, Проектная,Составитель В. Гороховедактор М. Петрова Техред Ж.Кастелевич Корректор СШе